散列表

淩亂°似流年 2021-09-26 14:26 425阅读 0赞

**直接寻址表**  
假设某个动态集合中的每个元素取自于U=\{0，1，2，…，m-1\}，这里的m不是一个很大的数，假设没有两个元素具有相同的关键字。我们用一个数组（**直接寻址表**），记为T\[0…m-1\]，其中的每个位置成为槽，对应全局区域中的一个关键字，如T\[k\]指向集合中关键字为k的元素，如果不存在k元素，则记为T\[k\]=null。  
优点：在U很小的情况下，插入、查找、删除的时间复杂度均为O(1)。  
缺点：在U很大的情况下，计算机的可用内存可能无法存储；若关键字集合远小于U，则会造成很大的空间浪费。  
**散列表**  
在散列表中，将存储需求降至了|O(K)|，同时保持了其查找元素的优势。在该方式下，关键字k存放在槽h(k)中，即利用散列函数h,由关键字计算出槽的位置，这里，函数h将关键字k的全局U映射到散列表T\[0…m\]的槽位上。

**散列函数**：  
好的散列函数的特点：h尽可能随机，即将关键字映射到同一个槽中的可能性尽可能降低。  
多数散列函数都假定关键字的全域为自然数集N=\{0,1,2…\}。因此，如果所给关键字不是自然数，则需要找到一种方式将其转换为自然数。例如字符串pt，可以转换为十进制整数对（112,116）（ASCII码表），然后以128为基数，pt即为关键字（112\*128）+116=14452。  
三种设计散列函数的方法：  
**除数散列法**  
h(k)=k mod m  
(m应该取不太接近2的整数幂的素数)  
**乘数散列法**  
h(k)=|m(kA mod 1)|(向下取整)  
(kA mod 1指的是取kA的小数部分，m的取值一般为2的某个幂次，A取(√5-1)/2是一个比较理想的值)  
**全域散列**（性能最好）  
随机地选择散列函数，使之独立于要存储的关键字。  
两个关键字可能会映射到同一个槽中，这种情况成为冲突。  
为了解决冲突，有两种方法：链接法和开放寻址法。  
**链接法**：  
把散列到同一槽中的所有元素都放在一个链表中。如果槽j中有一个指针，它指向存储所有散列到j的元素的链表的表头；如果不存在这样的元素，则槽j中为NULL。

**开放寻址法**：  
在开放寻址法中，所有元素都存放在散列表里，即每个表项或包含动态集合的的一个元素，或包含NIL。当查找某个元素时，要系统的检查所有的表项，知道找到所需的元素或者最终表明该元素不在表中。  
线性探查：  
![这里写图片描述][70]  
二次探查：  
![这里写图片描述][70 1]  
双重探查：  
![这里写图片描述][70 2]

[70]: /images/20210923/03ba5a8bbc7548e0b6ca4fa508742502.png
[70 1]: /images/20210923/aa356539ce33418f9747206ee920ef2f.png
[70 2]: /images/20210923/630245940e5547e09048ea5782414f31.png