Question

哈希表概念以及哈希冲突的处理

Answer 1

哈希表（散列表 Hash）是相对于线性表、树形结构的一种数据结构，它能在元素的存储位置和其关键字直接建立某种之间关系，那么在进行查找时，就无需做或者做很少次的比较，就能通过这个关系直接由关键字找到对对应的记录。这就是散列查找法（Hase Search）的思想，它通过对元素的关键字值进行某种运算，直接求出元素的地址。即使用关键字到地址的直接转换方法，而不需要反复比较。因此，散列查找法又叫杂凑法或者散列法。

选择一个好的散列函数可以在一定程度上减少冲突，但在实际应用中，很难完全避免发生冲突，所以选择一个有效的处理冲突的方法是散列表的另一个关键问题。
处理冲突的方法与散列表本身的组织形式有关。按组织形式的不同，通常分为两大类：开放地址法和链地址法。

开放地址法的基本思想是：把记录都存储在散列表数组中，当某一记录关键字key的初始散列地址H0=H(key)发生冲突时，以H0为基础，采取合适方法计算得到另一地址H1，如果H1仍然发生冲突，已H1位基础再求下一个地址H2，若H2仍然冲突，再求得H3，以此类推，直至Hk不发生冲突为止，则Hk为该记录在表中的散列地址。
根据计算方法，可以分为以下三种探测方法：

线性探测法会在出现在处理过程中发生冲突的发生第一个散列地址不同的记录争夺同一个后继散列地址的现象，称为二次聚集或者堆积。即在处理同义词的冲突过程中，又添加了非同义词的冲突。
它的优点是，只要散列表未满，就一定能找到一个不发生冲突的地址

而二次探测法和伪随机数探测法可以避免出现二次聚集现象，但是不保证一定能找到不发生冲突的地址。

链地址法的基本思想是：把具有相同散列地址的记录放在同一个单链表中，称为同义词链表。有m个散列地址就有m个单链表，同时用数组HT[0..m-1]存放各个链表的头指针，凡是散列地址为i的记录都以结点的方式插入已HT[i]为头结点的单链表中。