自己实现一个hashMap
数据结构
数组
数组是一系列元素的集合,数组的存储空间是连续的。特点是查找快,修改慢
链表
链表在内存中可以是不连续的。单向链表每个节点都会指向下一个几点。特点是查找慢,修改快。
hash表
结合上面两个的特点。产生了hash表。 通过hash算法计算出key在数组上的位置。达到了O(1)的时间复杂度。
但是,hash算法比较容易产生“冲突”,即即: key1!=key2,而 f (key1) = f(key2)。
Hash处理冲突方法
“处理冲突” 的实际含义是:为产生冲突的关键字寻找下一个哈希地址。
- 开放定址法
- 再哈希法
- 链地址法
- 开放定址法:
为产生冲突的关键字地址 H(key) 求得一个地址序列: H0, H1, H2, …, Hs 1≤s≤m-1,Hi = ( H(key) +di ) MOD m,
其中: i=1, 2, …, s,H(key)为哈希函数;m为哈希表长; - 再哈希法:
方法:构造若干个哈希函数,当发生冲突时,根据另一个哈希函数计算下一个哈希地址,直到冲突不再发生。
即:Hi=Rhi(key) i=1,2,……k,其中:Rhi——不同的哈希函数,特点:计算时间增加 - 链地址法:
将所有哈希地址相同的记录都链接在同一链表中。
Hash查找过程
对于给定值 K,计算哈希地址 i = H(K),若 r[i] = NULL 则查找不成功,若 r[i].key = K 则查找成功,
否则 “求 下一地址 Hi” ,直至r[Hi] = NULL (查找不成功) 或r[Hi].key = K (查找成功) 为止。
实现一个HashMap
- 实现
java.util.Map
- 支持hash查找
- 支持自动扩容
- 使用链地址法解决hash冲突
上代码:
HashMap 的长度为什么是2的幂次方
保存元素的时候需要根据key的hash值计算保存在hash表上的位置,就需要用%
运算来做。
但是,取余(%)操作的时候如果除数是2的幂次方则等价于与其除数减一取与(&)操作,
也就是 hash%length = hash&(length-1),length是2的幂次方。
因为&
操作比%
性能更高,
所以HashMap的长度就定为2的幂次方。
自己实现一个hashMap
https://www.wekri.com/java/hashMap/