在计算中 哈希表（哈希映射）是一种实现 字典操作的一种有效数据结构。尽管在最坏的情况下，哈希表中查找一个元素的时间与链表查找的时间相同，达到O(n)，在实际应用中，哈希查找的性能是几号的，在一些合理的假设下，在哈希表中查找一个元素的平军时间为O(1);

哈希函数

哈希函数是根据查找键得到元素在散列表中的整数下标。而如果将不同的键值映射到了同一个下标时，称为冲突

完美哈希函数将每个查找键映射为适合作为散列表索引的不同的整数

好的哈希函数应该是:

  • 具有做少的冲突
  • 计算要快
  • 均匀分布

具体的哈希函数的种类可以在维基百科中查看或者查看非加密型哈希函数

  1. //下面是数据结构与算法c中提供的函数
  3. Index hash(const char *key,int tableSize)
  4. {
  5.     unsigned int hashVal = 0;
  6.     while(*key!='\0')
  7.         hashVal = (hashVal<<5)+*key++;
  8.     return hashVal%TableSize
  9. }

以下是Unix ELF格式中使用的哈希算法实现

  1. unsigned long ElfHash(const unsigned char *s)
  2. {
  3.     unsigned long   h = 0, high;
  4.     while (*s)
  5.     {
  6.         h = (h << 4) + *s++;
  7.         if (high = h & 0xF0000000)
  8.             h ^= high >> 24;
  9.         h &= ~high;
  10.     }
  11.     return h;
  12. }

冲突的解决方法

分离链式法

其作法就是将散列到同一个值的所有元素保留到一个链表中，为了方便起见，这些表都有表头
ll.png
在执行插入或者查找时，我们先用哈希函数确定究竟遍历哪个链表，我们再在确定的链表中执行插入或者查找。这个提供了高效且简单的冲突解决方案，但改变了散列表的结构。所以链式法比开放地址需要更多的内存，且最坏情况下 链式发的效率可以退化到O(n),

开放寻址法(open addressing)

开放寻址法中所有的元素都存放在散列表中，也就是说每个表项或包含动态集合的一个元素，或者null,当查找某个元素时，要系统的检测所有表项，直到找到所需的元素，或者最终查明元素不在表中。
常见的开放寻址方法包括：

  • 线性探测,就是查取得哈希值之后，如果冲突，线性尝试表中的每个位置，直到找到合适的位置
  • 平方探测。
  • 双散列

除了上面的还有其他的散列:

布谷鸟散列(Cuckoo hashing)

跳房子散列(Hopscotch hashing)

罗宾汉散列(Robin Hood hashing)