logo头像
Snippet 博客主题

自己实现一个hashMap

数据结构

数组

数组是一系列元素的集合,数组的存储空间是连续的。特点是查找快,修改慢

链表

链表在内存中可以是不连续的。单向链表每个节点都会指向下一个几点。特点是查找慢,修改快。

hash表

结合上面两个的特点。产生了hash表。 通过hash算法计算出key在数组上的位置。达到了O(1)的时间复杂度。

但是,hash算法比较容易产生“冲突”,即即: key1!=key2,而 f (key1) = f(key2)。

Hash处理冲突方法

“处理冲突” 的实际含义是:为产生冲突的关键字寻找下一个哈希地址。

  • 开放定址法
  • 再哈希法
  • 链地址法
  1. 开放定址法:
    为产生冲突的关键字地址 H(key) 求得一个地址序列: H0, H1, H2, …, Hs 1≤s≤m-1,Hi = ( H(key) +di ) MOD m,
    其中: i=1, 2, …, s,H(key)为哈希函数;m为哈希表长;
  2. 再哈希法:
    方法:构造若干个哈希函数,当发生冲突时,根据另一个哈希函数计算下一个哈希地址,直到冲突不再发 生。
    即:Hi=Rhi(key) i=1,2,……k,其中:Rhi——不同的哈希函数,特点:计算时间增加
  3. 链地址法:
    将所有哈希地址相同的记录都链接在同一链表中。

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冲突

上代码:

微信打赏

赞赏是不耍流氓的鼓励