首页 > 代码库 > 散列表
散列表
如果表够大，散列函数足够好，那么散列表在查找上具有O(1)的时间复杂度。
但是我们考虑出现冲突的情况，如果使用分离链表法来处理冲突。那么链表的平均长度等于装填因子a（元素个数与散列表大小的比值）的大小。所以不成功查找的复杂度为a，成功查找的复杂度为1 + a/2。
代码实现如下：
1 #include <cstdio> 2 #include <cstdlib> 3 #include <cmath> 4 #include <cstring> 5 // 分离链接散列表 6 typedef unsigned int index; 7 typedef int itemType; 8 typedef struct ListNode *position; 9 typedef position list; 10 typedef struct HashTable *hashTable; 11 12 struct ListNode { 13 itemType item; 14 position next; 15 }; 16 struct HashTable { 17 int tableSize; 18 list *listArr; 19 }; 20 21 int 22 NextPrime(int n) 23 { 24 int ceiling, isPrime; 25 26 isPrime = 0; 27 ceiling = 2 * n; 28 29 for ( ; n < ceiling; n++) { 30 int nSqrt = (int)sqrt(n); 31 isPrime = 1; 32 for (int i = 2; isPrime && i <= nSqrt; i++) 33 { 34 if (n % i == 0) { 35 isPrime = 0; 36 } 37 } 38 if (isPrime) { 39 return n; 40 } 41 } 42 } 43 44 index 45 Hash(itemType key, int tableSize) 46 { 47 return key % tableSize; 48 } 49 50 hashTable 51 InitializeTable(int tableSize) 52 { 53 hashTable h; 54 55 h = (hashTable)malloc(sizeof(struct HashTable)); 56 if (h == NULL) { 57 printf("Out of space!\n"); 58 exit(-1); 59 } 60 61 h->tableSize = NextPrime(tableSize); 62 63 h->listArr = (list*)malloc(sizeof(list) * h->tableSize); 64 // 65 if (h->listArr == NULL) { 66 printf("Out of space!\n"); 67 exit(-1); 68 } 69 70 memset(h->listArr, 0, h->tableSize * sizeof(list*)); 71 72 return h; 73 } 74 75 position 76 Find(itemType key, hashTable h) 77 { 78 list l; 79 80 l = h->listArr[Hash(key, h->tableSize)]; 81 82 for ( ; l != NULL; l = l->next) { 83 //printf("%d\n", Hash(key, h->tableSize)); 84 if (l->item == key) { 85 //printf("here\n"); 86 return l; 87 } 88 } 89 90 return NULL; 91 } 92 93 void 94 Insert(itemType key, hashTable h) 95 { 96 position p, newNode; 97 list l; 98 99 p = Find(key, h);100 101 int hValue = http://www.mamicode.com/Hash(key, h->tableSize);102 103 if (p == NULL) {104 newNode = (position)malloc(sizeof(struct ListNode));105 if (newNode == NULL) {106 printf("Out of space!\n");107 exit(-1);108 }109 /* 错误的方法，只改变了 l 这个指针，却没变动listArr[hValue]本身。 110 list l = h->listArr[hValue];111 newNode->next = l;112 newNode->item = key;113 l = newNode;114 //h->listArr[hValue] = newNode;115 */116 117 newNode->item = key;118 newNode->next = h->listArr[hValue];119 h->listArr[hValue] = newNode;120 printf("key %d inserted at position %d.\n", h->listArr[hValue]->item, Hash(key, h->tableSize));121 122 }123 }124 125 int126 main(int argc, char** argv)127 {128 hashTable h;129 130 h = InitializeTable(10);131 132 for (int i = 0; i < 10; i++) {133 Insert(i*i, h);134 }135 136 137 for (int i = 0; i < 100; i++) {138 if (Find(i, h)) {139 printf("key: %d found.\n", i);140 } else {141 printf("key: %d not found.\n", i);142 }143 }144 145 146 system("pause");147 return 0;148 }
-
另外，当我们使用开放定址法来处理冲突的时候，特别要注意删除的时候，不能直接删除。原因是如果你删除了P这个位置的元素x。那么如果以前有的元素y应该映射到P，却因为冲突而到了其他地方。当x被删除之后，P这个位置为空。那么如果我们要寻找y，就会第一个找到P这个位置，发现为空。于是就找不到y了。（可以继续遍历开放定址法的位置来寻找y……但是这样子不是太楞了吗？如果原本就没y这个元素呢，那我们得做许多无用功。）
不能直接删除，所以一般我们使用懒惰删除，给P位置一个“已删除”的标记，就能解决这个问题了。
散列表
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。