数据结构 二叉树遍历 >HashMap、Hashtable实现原理

本来继List的整理后会继续Collection下面的另一个分支Set的，但是看了下HashSet的实现是基于HashMap的，所以先从Map着手，然后在整理Set的

环境JDK8

一、存储原理

1、HashMap的存储

我们先来看看HashMap的部分实现源码：

通过成员变量以及HashMap的内部类Node，我们不难发现其存储主体是具有类似链表结构的Node和Node数组table

为了更形象的了解数据结构，我们先来看看HashMap存储的数据（如果链表大小超过8，那么链表会刷新成二叉树的形式，Hashtable就没有这种待遇）：

HashMap相当于结合了数组与链表的数据结构，我们成为哈希表，在Map进行put操作增加数据的时候，会根据key值的hashCode以及table（数组）大小的余数来决定新的数据应该存储在哪个数组项目里面，并且对该数组项里面的链表数据一一比较，如果有相同key的那么记性value更新，如果没有相同key的那么在链表的末尾加上新的数据。当哈希表中的条目数超出了加载因子与当前容量的乘积时，则要对该哈希表进行 rehash 操作（即重建内部数据结构），从而哈希表将具有大约两倍的容量。数据结构 二叉树遍历

2、Hashtable的存储

下面是Hashtable的部分实现源码

不难看出，除了部分参数外Hashtable的数据存储结构跟HashMap的基本无差别，都是由具有链表结构特性的内部类Entry和Entry数组table组成的。那么这两种存储结构究竟有什么不同的地方呢，我们来分析具体的方法实现

二、功能实现分析

1、put(K key, V value)的实现

（1）HashMap的put实现代码解析

上面的代码我们看出HashMap调用put的方法时，会对key进行二次Hash编码然后在通过求余数的方式获取table的数组下标位置，如果该位置无值时直接进行节点赋值，如果有位置那么通过遍历链表（或者二叉树）数据结构进行对比如果有hashCode和equals都符合的那么进行值替换，如果没有那么在末尾追加，如果判断单个列表的长度达到8那么将链表替换成二叉树，如果整个的HashMap长度超过map容器的阈值（阈值为table的大小-默认16以及加载因子factor-默认0.75的乘积），那么进行2倍扩容重新排列。数据结构 二叉树遍历如果因子值太小会造成平凡扩容影响写的性能，如果因子值过大影响查询的性能（取决于链表的大小）

（2）Hashtable的put实现代码解析

比较明显的一个特征put方法有synchronized修饰，表明Hashtable的put方法时线程安全的，那么其获取key的hashcode也是直接获取的hashCode编码，比较固定的数组加链表形式没有HashTable的二叉树结构存储，链表加入的方式是加到头部而不是尾部，其它方式与

HashMap基本类似，甚至更简单，数组的最大长度是Integer.MAX_VALUE - 8，超过容器阈值（阈值为table的大小-默认11以及加载因子factor-默认0.75的乘积）扩容的大小是2n+1

2、get(K key)的实现

（1）HashMap的get实现代码解析

get的实现思路相对比较清晰，先对key进行二次hashcode编码，然后计算出键值对应该所处的数组项，剩下的就是对链表或者二叉树进行遍历对比找出节点（对比依据key的二次hashcode编码一致，equals结果一致）

（2）Hashtable

思路跟HashMap类似，获取编码，计算下标，遍历链表进行对比找出节点。

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-74528-1.html