分类导航

java——HashMap的实现原理，自己实现简单的HashMap

发布时间：2016年12月28日作者：文章转自网络，版权归原作者所有，反馈可立刻删除 (该文来自笔记，点击查看原文)

数据结构中有数组和链表来实现对数据的存储，但是数组存储区间是连续的，寻址容易，插入和删除困难；而链表的空间是离散的，因此寻址困难，插入和删除容易。

因此，综合了二者的优势，我们可以设计一种数据结构——哈希表（hash table），它寻址、插入和删除都很方便。在java中，哈希表的实现主要就是HashMap了，可以说HashMap是java开发中使用最多的类之一吧。

HashMap的底层其实就是链表的数组，代码为

transient Entry[] table;

这里的table其实就是一个链表的数组，因为我们的数据是二元的，因此HashMap定义了一个内部的类Entry，它包含了key和value两个属性。这样一个一维的线性数组就可以存储两个值了。同时Entry是一个链表，因此还有一个Entry next属性，它指向了下一个节点。

存储put时：

首先计算出key的hash,然后用table[hash]得到那个链表，再遍历这个链表，如果链表中有一个key和这个key是满足equals的话，则将value替换掉；如果没有的话，则插入到链表的尾部。

int h = hash(key);
Entry e = table[h];