内容简介:通过哈希桶来实现的k/v存储,通过key的hash码,再进行桶计算,生成一个在某个范围内的值,这就是桶的索引号,再把值存储到桶对应的entry里,桶bucket存储了entry的索引号,通过一个bucket可以直接或者间接找到一个entry.graph LR key-->hashcode hashcode-->bucket桶运算 bucket桶运算-->得到bucket索引 得到bucket索引-->bucket值就是entry的索引 bucket值就是entry的索引-->x("↓")graph LR b
两个数组
- bucket数组:存储key的hash桶,桶指的是把hashcode分配到一定的范围内
- entry数组:用来存储实现的值,它是一个单向链表,bucket总是存储链表的最后一个元素
实现方式
通过哈希桶来实现的k/v存储,通过key的hash码,再进行桶计算,生成一个在某个范围内的值,这就是桶的索引号,再把值存储到桶对应的entry里,桶bucket存储了entry的索引号,通过一个bucket可以直接或者间接找到一个entry.
- 直接找到:当hash没有冲突时,它存储的就是真实的entry索引
- 间接找到:当hash出现冲突(碰撞)时,它就会把当前最后的索引赋值这个新entry.next,而新的entry的索引就是现在的bucket的值。
实现流程图
graph LR key-->hashcode hashcode-->bucket桶运算 bucket桶运算-->得到bucket索引 得到bucket索引-->bucket值就是entry的索引 bucket值就是entry的索引-->x("↓")
graph LR bucket值就是entry的索引-->冲突解决 冲突解决-->单向链表next指向上一个值 单向链表next指向上一个值-->单身链表查找 单身链表查找-->返回结果
数组长度为素数
hash桶数全部使用的是质数,因为我们在hash的定义中,hash函数使用的是标准的求模函数,因此这样定义桶数有利于元素各个桶之间的 均匀分布
和 减少hash相同值的碰撞概率
。
例如:
举一个有点极端的例子,假设我们的元素全是偶数1,4,6,8,10,12,14,1,6,18,20,22 如果我们使用4个桶: 0: 4,8,12,16.20 1: 2:6,10,14,18,22 3: 很明显看出有的桶有很多元素,但是有的桶是空桶,如果我们改为使用3个桶: 0: 6,12,18 1:4,10,16,22 2:2,8,14,20
模拟一个字典的实现
@Getter @Setter class KVPair<K, T> { private K key; private T value; private int hashCode; private int next; //下一个元素的下标索引,如果没有下一个就为-1 } /** * 模拟实现一个字典kv结构. * * @param <T> */ class MokiHashMap<K, T> { static int[] primes = { 3, 7, 11, 17, 23, 29, 37, 47, 59, 71, 89, 107, 131, 163, 197, 239, 293, 353, 431, 521, 631, 761, 919, 1103, 1327, 1597, 1931, 2333, 2801, 3371, 4049, 4861, 5839, 7013, 8419, 10103, 12143, 14591, 17519, 21023, 25229, 30293, 36353, 43627, 52361, 62851, 75431, 90523, 108631, 130363, 156437, 187751, 225307, 270371, 324449, 389357, 467237, 560689, 672827, 807403, 968897, 1162687, 1395263, 1674319, 2009191, 2411033, 2893249, 3471899, 4166287, 4999559, 5999471, 7199369}; // 桶数组 private int[] buckets;// 最新的entry的索引号, // 真实的数据 private KVPair<K, T>[] entry; // entry根据next形成一个单链表 private int count = 0; // 当前entries的数量 public MokiHashMap() { buckets = new int[3]; entry = new KVPair[3]; for (int i = 0; i < buckets.length; i++) { buckets[i] = -1; } } private void reSize() { int newLength = getPrime(count); int[] newBuckets = new int[newLength]; for (int i = 0; i < newBuckets.length; i++) { newBuckets[i] = -1; } KVPair<K, T>[] newEntries = new KVPair[newLength]; System.arraycopy(entry, 0, newEntries, 0, count); System.arraycopy(buckets, 0, newBuckets, 0, count); entry = newEntries; buckets = newBuckets; } /** * 得到某个key所在的hash桶 * * @param key . * @return */ private int getHashBucketIndex(K key) { int len = buckets.length; int hashCode = key.hashCode(); int index = hashCode & (len - 1);//len升级的hash桶 return index; } /** * 得到较大的素数. * * @param min . * @return */ private int getPrime(int min) { if (min < 0) { throw new IllegalArgumentException("最小为3"); } for (int i = 0; i < primes.length; i++) { int prime = primes[i]; if (prime > min) return prime; } return min; } public void add(K key, T value) { if (count == entry.length) { reSize(); } int index = getHashBucketIndex(key); int entryIndex = buckets[index]; entry[count] = new KVPair(); if (entryIndex < 0) { entry[count].setNext(-1); } else { entry[count].setNext(buckets[index]); } entry[count].setHashCode(index); entry[count].setKey(key); entry[count].setValue(value); buckets[index] = count; count = count + 1; } public T find(K key) { int entryIndex = buckets[getHashBucketIndex(key)]; while (entry[entryIndex].getNext() > -1) { if (entry[entryIndex].getKey().equals(key) && entry[entryIndex].getHashCode() == getHashBucketIndex(key)) { return entry[entryIndex].getValue(); } entryIndex = entry[entryIndex].getNext(); } return null; } } public class KVTest { @Test public void testDic() { MokiHashMap<String, String> dic = new MokiHashMap<>(); dic.add("ok", "1"); dic.add("zzl", "2"); dic.add("lr", "3"); dic.add("dd", "1"); dic.add("a", "b"); dic.add("b", "c"); dic.add("d", "e"); dic.add("e", "f"); System.out.println("dic find:" + dic.find("a")); } }
以上所述就是小编给大家介绍的《字典哈希表的实现原理》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!
猜你喜欢:本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。
数据压缩导论(第4版)
[美] Khalid Sayood / 贾洪峰 / 人民邮电出版社 / 2014-1 / 129.00
数据压缩已经成为信息革命的一门支撑技术,这场革命已经改变了我们的生活,而在此过程中,数据压缩也变得几乎无处不在。从MP3播放器到智能手机,再到数字电视和数字电影,数据压缩几乎成了所有信息技术的必备要素。 近年来,以大数据为标志的互联网技术高歌猛进。数据规模大、产生速度快、来源多样等特性,导致数据存储和处理都前所未有地复杂。《数据压缩导论(第4版)》作为迄今为止数据压缩领域最全面而深入的著作,......一起来看看 《数据压缩导论(第4版)》 这本书的介绍吧!