哈希表
2020-11-10 本文已影响0人
Sweet丶
哈希表（Hash Table）也称为散列表，使用数组来存、取元素，每个元素有自己对应的key，通过key能快速确定元素的位置，相比在数组中遍历查找值有更高的效率。哈希表的基本思路是将Key经过哈希函数计算后得到在数组中的下标，然后将元素存放在这个位置。
一、哈希函数要做什么？
哈希函数要做到的是将Key进行运算得到最终得到该存放的下标值Index。哈希计算需要注意几点：
- 计算哈希值的方式尽量简单点。
- 尽量减少不同key产生相同的地址（哈希冲突）。
- 在数组中存储的位置分布相对均匀。
常见的哈希算法有：
- 除法散列法
对数组长度取余，index = key % 数组长度
- 平方散列法
index = (key * key) >> 28 （右移，除以2^28。记法：左移变大，是乘。右移变小，是除。）
- 斐波那契（Fibonacci）散列法
二、hash冲突的解决办法
不同的Key通过哈希函数运算得到的下标极有可能是相同的，这个时候如何办？
哈希冲突的解决办法有两种：
1. 开放地址法，在产生的下标值发生冲突时，对这个值再进行一次运算得到新的下标，若再冲突则再次运算，直到不冲突，这个在iOS中CFDidictionary和CFSet中都是用的这种方式。
再次运算的方式：
- 线性探测再散列：(Index+1) % 数组长度。
- 二次探测再散列：（Index ± 1）%数组长度。
- 伪随机数探测再散列：提前根据数组长度生成随机数序列，冲突时将随机数作为下次探测的地址。
2. 链表法（也称拉链法、位桶法）
数组存放的元素改为链表头结点，在冲突时将value存放在链表的下一个元素。
三、哈希表扩容
在哈希表已经满了的时候，我们要存放新元素时将不得不扩容，但其实系统的做法却不会等到满了再扩容，系统会在哈希表装的元素达到一定的比例时就会扩容（比如达到0.75时），为什么呢？
减少哈希冲突除了在哈希函数下功夫，提前扩容也是很必要的。
- 扩容做的事是什么？就是先对数组扩容，扩容多少合适呢？
下面是iOS系统的CFSet实现原理中哈希表扩容方式，仅供参考：
static const uint32_t __CFSetCapacities[42] = {
4, 8, 17, 29, 47, 76, 123, 199, 322, 521, 843, 1364, 2207, 3571, 5778, 9349,
15127, 24476, 39603, 64079, 103682, 167761, 271443, 439204, 710647, 1149851, 1860498,
3010349, 4870847, 7881196, 12752043, 20633239, 33385282, 54018521, 87403803, 141422324,
228826127, 370248451, 599074578, 969323029, 1568397607, 2537720636U
};
- 扩容好数组后，把原来的元素经过哈希函数移动到新数组中，这样就完成了扩容了。
四、思维发散
在我们使用字典时，有个方法是包含容量opicity参数的，我们在创建字典时可以填入一个合适的值，这样能减少扩容的次数。
NSUInteger suitableCount = 10; // 你使用时初始的量多少个
NSMutableDictionary *dic = [NSMutableDictionary dictionaryWithCapacity: suitableCount];
