HashMap实现原理深究

文章目录

1. 实现原理：
1. 1.1. 构造方法
2. 1.2. put/get方法
2. get方法
1. 2.0.1. 什么是native修饰符

3.1. HashMap、HashSet的特性与区别
3.2. HashMap、HashTable区别
3.3. HashMap、TreeMap的区别
3.4. HashMap、LinkedHashMap区别

最近被问到HashMap的原理比较多；

HashMap继承自AbstractMap抽象类，而AbstractMap实现了Map接口
HashMap允许设置空(null)值
HashMap的方法不是同步的，是异步的，因此不是线程安全的。
HashMap中数据是无序的。有序的参见TreeMap和LinkedHashMap。

实现原理：

HashMap如何使用：

HashMap map = new HashMap();
map.put(“key”,”value”);

构造方法

new HashMap 是调用构造方法初始化对象，它有几个构造方法：
\1.
//initialCapacity是初始化空间大小，loadFactor是装载空间数，影响读取与写入的使用线程数量
public HashMap(int initialCapacity, float loadFactor)
{
……..
}

初始化空间大小

public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
默认构造方法
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}

put/get方法

public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}

public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}

好像挻简单的，但是它里面做了多少事情呢？再继续看；

/**
Implements Map.put and related methods
 *
@param hash hash for key
@param key the key
@param value the value to put
@param onlyIfAbsent if true, don't change existing value
@param evict if false, the table is in creation mode.
@return previous value, or null if none
 */
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
   boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}

put的方法做了这么多事，首先putVal方法有五个参数：

hash: key所对应的hash数值(重新作了运算的)

看源码发现，返回的是一个数值：
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

key.hashCode()是Object的原始方法，返回的是对象的hashCode值，是数字。返回的是java的System类的静态native值(什么是native修饰符，等下解释)：
/**
Returns the same hash code for the given object as
would be returned by the default method hashCode(),
whether or not the given object’s class overrides
hashCode().
The hash code for the null reference is zero.
*
@param x object for which the hashCode is to be calculated
@return the hashCode
@since JDK1.1
*/
public static native int identityHashCode(Object x);

而返回的hashCode并非真正的原始object的hashCode值，而是作了逻辑异或运算，h>>>16代表将hashCode值向右移位16位后的值，是让hashCode与它作逻辑异或运算得到的值，相当于加了一层密。

key: 键名
value:存储元素
onlyIfAbsent: if true, don’t change existing value,默认是false
evict:if false, the table is in creation mode. in creation mode 是什么模式？
evict根据后面的代码看，这个参数在HashMap里是不起作用的，因为在putVal里调用了afterNodeInsertion(evict);，但是我点进去，发现并没有实现：
void afterNodeInsertion(boolean evict) { }

但是我看到linkedHashMap有实现：

void afterNodeInsertion(boolean evict) { // possibly remove eldest
LinkedHashMap.Entry<K,V> first;
if (evict && (first = head) != null && removeEldestEntry(first)) {
K key = first.key;
removeNode(hash(key), key, null, false, true);
}
}

猜测是将值置于链表组之后。

接下来我们再来分析putVal方法实现，可以发现，HashMap是用一个Node对象的数组结构来存元素数据的：
Node<K,V>[] tab; Node<K,V> p; int n, i;

再看Node元素的组成：
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
……..
}

有四个元素，hash值，key值，value，还有个承接下个节点的node对象：next,这个是一个典型的链表结构。

关键代码：
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;

这段对存储的规则说的很明确了，除了非空规则，还调用了equals方法判断，如果key值的类型是String，那equals就好说，如果是其它类型呢？

关键代码：

n = (tab = resize()).length;
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);

使用快速定位的方法，如果得到的下标值没有对象，则作为新添加的对象处理，而下标值的算法是：(n-1)&hash，作了逻辑与且的运算。

关键代码：

if (++size > threshold)
resize();

意思是HashMap的数组大小超过了某个限定值，就执行resize方法。
这里的threshold是什么？resize方法又是什么？

源码：
/** * The next size value at which to resize (capacity * load factor).
* * @serial
*/
// (The javadoc description is true upon serialization.
// Additionally, if the table array has not been allocated, this
// field holds the initial array capacity, or zero signifying
// DEFAULT_INITIAL_CAPACITY.)
int threshold;

先猜猜意思，好像是说，如果数组表没有被分配内存空间，这个字段会保存初始化数组容量，或者显示0，默认值是：DEFAULT_INITIAL_CAPACITY

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

用google翻译出来：

序列化时javadoc的描述是正确的。
另外，如果表数组尚未分配，则该字段保持初始数组容量或零表示

感觉一头雾水，这个玩意到底是干什么的？

再看看后面的resize方法，看用这个字段来做什么判断没有。

final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
if (oldCap > 0) {
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
 oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
else {               // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
  (int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // preserve order
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}

这个方法体好长啊。。。。。
从源码上看，个人觉得主要是用来判断map的链表数组有没有超出初始化时数组空间的大小，如果超出了则给数组扩容。
// 如果超过了最大内存空间设置，则给threshold赋予Integer的最大值上限，并返回，这里的判断其实是说，数组大小其实已经超出了，就只要给threshold赋值就好了，直接返回老的数组就行了
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}

关键代码：

else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
else {               // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}

这是给threshold分配大小的默认算法，有值就用原来的值，没值就赋值：
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);

然后接下来的代码就是将原来的数组重新取出再重新组装排列一个新数组并返回，这样的话，原来的顺序就乱了，这就是HashMap无序的原因了。

get方法

那看了put的关键代码后，再来看get的代码就简单得多了：

public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}


final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
if ((e = first.next) != null) {
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}

什么是native修饰符

A native method is a Java method whose implementation is provided by non-java code.

这是介绍，看字面意思，是提供给java调用非java代码实现用的，就是说加了native这个关键字，java就能调用非java实现的代码了。

而java解析器是用C语言实现的，JVM调用的object的hashCode方法我们方法在源码里没有实现体，但是执行一下又有值返回，那这就说明这个方法的实现是解释器用C实现的，而解释器只提供了访问API。

与其它类似容器的区别

HashMap、HashSet的特性与区别

HashSet实现Set接口，而HashMap实现Map接口，Set是Collection接口的子类,Map接口上层是Object类，HashMap没有实现Collection接口，是独立于collection集合之外的。它们同属于com.util包中。
1. HashSet的内部是通过引用HashMap作为成员变量实现的.
  默认构造方法：
  public HashSet() {
  map = new HashMap<>();
  }
2. HashMap没有collection 接口的contains方法，取而代之的是containsKey和containsValue
3. HashSet的contains方法调用的是HashMap的containsKey实现的。
4. HashSet使用add方法添加对象,HashMap使用put方法。
5. HashSet只存对象，HashMap存键值对。

HashSet的add方法：

public boolean add(E e) {
return map.put(e, PRESENT)==null;
}

HashSet的contains方法：
public boolean contains(Object o) {
return map.containsKey(o);
}

HashMap、HashTable区别

HashMap是非线程安全的，由于HashTable中的所有方法都是同步方法，所以它是线程安全的。
HashMap的键和值都允许有null值存在，而HashTable则不行。
因为线程安全的问题，HashMap效率比HashTable的要高。
HashMap中数据是无序的(resize)，HashTable也是无序的(rehash)
都实现了map接口，HashMap继承于AbstractMap类,HashTable继承于Dictionary类
HashMap添加时，key是重新计算的hashcode,而HashTable直接使用的是key的Object的原始hashCode，添加到数组时的下标计算方法也不一样

Dictionary 类主要方法：

abstract public int size();
abstract public boolean isEmpty();
abstract public Enumeration<K> keys();
abstract public Enumeration<V> elements();
abstract public V get(Object key);
abstract public V put(K key, V value);
abstract public V remove(Object key);

HashMap、TreeMap的区别

HashMap是无序的(其实是resize方法打乱的)，TreeMap是有序的
HashMap是基于Node链表实现的，而TreeMap是基于红黑树这种二叉树算法实现的
TreeMap继承了SortMap,默认使用key的自然排序算法给元素排序，所以是相对HashMap来说是有序的(关于如何自然排序，请参考TreeMap自然排序源码分析)

HashMap、LinkedHashMap区别

同为链表实现
*

小黑的技术博客

不积跬步无以至千里

HashMap实现原理深究

实现原理：

构造方法

put/get方法

get方法

什么是native修饰符

与其它类似容器的区别

HashMap、HashSet的特性与区别

HashMap、HashTable区别

HashMap、TreeMap的区别

HashMap、LinkedHashMap区别