本文主要讲多阶HASH表的结构。
1. 多阶hash表实际上是一个锯齿数组，看起来是这个样子的：
■■■■■■■■■■■■■■■
■■■■■■■■■■■■■
■■■■■■■■■■
■■■■■■
■■■
每一行是一阶，上面的元素个数多，下面的元素个数依次减少。
每一行的元素个数都是素数的。
2. 数组的每个节点用于存储数据的内容，其中，节点的前四个字节用于存储int类型的key或者是hash_code
3. 创建多阶HASH的时候，用户通过参数来指定有多少阶，每一阶最多多少个元素。
那么，下面的每一阶究竟应该选择多少个元素呢？从代码注释上看来，是采用了素数集中原理的算法来查找的。
例如，假设每阶最多1000个元素，一共10阶，则算法选择十个比1000小的最大素数，从大到小排列，以此作为各阶的元素个数。通过素数集中的算法得到的10个素数分别是：997 991 983 977 971 967 953 947 941 937。
可见，虽然是锯齿数组，各层之间的差别并不是很多。
4. 查找过程：
先将key在第一阶内取模，看是否是这个元素，如果这个位置为空，直接返回不存在；如果是这个KEY，则返回这个位置。
如果这个位置有元素，但是又不是这个key，则说明hash冲突，再到第二阶去找。
循环往复。
5. 好处：
1. hash冲突的处理非常简单；
2. 有多个桶，使得空间利用率很高，你并不需要一个很大的桶来减少冲突。
3. 可以考虑动态增长空间，不断加入新的一阶，且对原来的数据没影响。
没有评论:
发表评论