【Java】JDK1.8 HashMap解析

JDK1.8 HashMap解析

WillLiaowh发布于 今天 09:49

数据结构

JDK1.8的HashMap采用数组+单链表+红黑树的数据结构,数组和链表存储的是一个个Node对象,红黑树存储的是TreeNode对象
【Java】JDK1.8 HashMap解析

Node

    static class Node<K,V> implements Map.Entry<K,V> {

final int hash;

final K key;

V value;

Node<K,V> next;

}

TreeNode

    static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {

TreeNode<K,V> parent; // red-black tree links

TreeNode<K,V> left;

TreeNode<K,V> right;

TreeNode<K,V> prev; // needed to unlink next upon deletion

boolean red;

TreeNode(int hash, K key, V val, Node<K,V> next) {

super(hash, key, val, next);

}

final TreeNode<K,V> root() {

for (TreeNode<K,V> r = this, p;;) {

if ((p = r.parent) == null)

return r;

r = p;

}

}

}

常用方法

常用API

V get(Object key); //获得指定key的值

V put(K key, V value); //添加key-value对

void putAll(Map<? extends K, ? extends V> m); //将指定Map中的key-value对复制到此Map中

V remove(Object key); //删除该key-value

boolean containsKey(Object key); //判断是否存在该key的key-value对;是则返回true

boolean containsValue(Object value); //判断是否存在该value的key-value对;是则返回true

Set<K> keySet(); //单独抽取key序列,将所有key生成一个Set

Collection<V> values(); //单独value序列,将所有value生成一个Collection

void clear(); // 清除HashMap中的所有key-value对

int size(); // 返回HashMap中所有key-value对的数量

boolean isEmpty(); // 判断HashMap是否为空,size == 0时表示为空

使用

public class HashMapTest {

public static void main(String[] args) {

/**

* 1. 声明1个 HashMap的对象

*/

Map<String, Integer> map = new HashMap<String, Integer>();

/**

* 2. 向HashMap添加数据(放入键-值对)

*/

map.put("Java", 1);

map.put("HashMap", 2);

map.put("List",3);

map.put("set",4);

/**

* 3. 获取 HashMap 的某个数据

*/

System.out.println("" + map.get("HashMap"));

/**

* 4. 遍历HashMap共有3种方法:分别针对Entry或key或value

* 步骤1:获得Entry或key或value的集合

* 步骤2:遍历,使用for循环或迭代器Iterator

*/

// 方法1:获得Entry的Set集合再遍历

// 获得Entry的Set集合

Set<Map.Entry<String, Integer>> entrySet = map.entrySet();

// 通过for循环遍历

for(Map.Entry<String, Integer> entry : entrySet){

System.out.print(entry.getKey());

System.out.println(entry.getValue());

}

// 通过迭代器遍历

// 先获得Entry的Iterator,再循环遍历

Iterator iter1 = entrySet.iterator();

while (iter1.hasNext()) {

// 遍历时,需先获取entry,再分别获取key、value

Map.Entry entry = (Map.Entry) iter1.next();

System.out.print((String) entry.getKey());

System.out.println((Integer) entry.getValue());

}

// 方法2:获得key的Set集合再遍历

Set<String> keySet = map.keySet();

// 通过for循环

for(String key : keySet){

System.out.print(key);

System.out.println(map.get(key));

}

// 通过迭代器遍历

// 先获得key的Iterator,再循环遍历

Iterator iter2 = keySet.iterator();

String key = null;

while (iter2.hasNext()) {

// 遍历时,需先获取key,再获取value

key = (String)iter2.next();

System.out.print(key);

System.out.println(map.get(key));

}

// 方法3:获得value的集合再遍历

Collection valueSet = map.values();

// 获得values的Iterator,再循环遍历

Iterator iter3 = valueSet.iterator();

while (iter3.hasNext()) {

System.out.println(iter3.next());

}

}

}

对于遍历方式,推荐使用针对 key-value对(Entry)的方式:效率高

  1. 对于遍历keySet,valueSet,实质上遍历了2次:
    第1次,for/iterator迭代器遍历;
    第2次 从HashMap中取出key的value操作
  2. 对于遍历entrySet,实质遍历了1次for/iterator迭代器遍历,Entry已经存储了key和 value

源码分析

主要属性

//默认容量

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;

//最大容量

static final int MAXIMUM_CAPACITY = 1 << 30;

//加载因子

static final float DEFAULT_LOAD_FACTOR = 0.75f;

//扩容阈值 = 容量 x 加载因子,当哈希表的大小 ≥ 扩容阈值时,就会扩容哈希表

int threshold

//存储数据的Node类型数组,长度=2的幂

transient Node<K,V>[] table;

//HashMap中存储的键值对的数量

transient int size

// 链表的树化阈值,即链表转成红黑树的阈值,当Node链表长度>该值时,则将链表转换成红黑树

static final int TREEIFY_THRESHOLD = 8;

// 链表的还原阈值,即红黑树转为链表的阈值,当在扩容时,HashMap的数据存储位置会重新计算,在重新计算存储位置后,当红黑树内TreeNode数量 < 6时,则将 红黑树转换成链表

static final int UNTREEIFY_THRESHOLD = 6;

// 最小链表树化容量阈值,即 当Node数组长度 > 该值时,才允许树形化链表,否则则直接扩容,而不是树形化

static final int MIN_TREEIFY_CAPACITY = 64;

构造方法

    //加载因子,容量可指定

public HashMap(int initialCapacity, float loadFactor) {

if (initialCapacity < 0)

throw new IllegalArgumentException("Illegal initial capacity: " +

initialCapacity);

if (initialCapacity > MAXIMUM_CAPACITY)

initialCapacity = MAXIMUM_CAPACITY;

if (loadFactor <= 0 || Float.isNaN(loadFactor))

throw new IllegalArgumentException("Illegal load factor: " +

loadFactor);

this.loadFactor = loadFactor;

this.threshold = tableSizeFor(initialCapacity);

}

//加载因子等于默认值,容量可指定

public HashMap(int initialCapacity) {

this(initialCapacity, DEFAULT_LOAD_FACTOR);

}

//默认构造函数,加载因子,容量等于默认值

public HashMap() {

this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted

}

//可传入一个map的构造函数

public HashMap(Map<? extends K, ? extends V> m) {

this.loadFactor = DEFAULT_LOAD_FACTOR;

putMapEntries(m, false);

}

put()方法

    public V put(K key, V value) {

return putVal(hash(key), key, value, false, true);

}

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,

boolean evict) {

Node<K,V>[] tab; Node<K,V> p; int n, i;

//1. 若Node数组为空,则通过resize()初始化数组

if ((tab = table) == null || (n = tab.length) == 0)

n = (tab = resize()).length;

//2.计算key存放Node数组中的数组下标,判断这个数组下标Node数组上是否有Node存在

//2.1若不存在,则在该位置新建一个Node节点

if ((p = tab[i = (n - 1) & hash]) == null)

tab[i] = newNode(hash, key, value, null)

//2.2若存在

else {

Node<K,V> e; K k;

//2.1.1判断key是否与数组上的Node里面的key是否相同,是则用新的value值替换旧的value值

if (p.hash == hash &&

((k = p.key) == key || (key != null && key.equals(k))))

e = p;

//2.1.2若不相同,判断当前Node是红黑树,则在树中插入或更新键值对

else if (p instanceof TreeNode)

e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);

//2.1.3若不相同,判断当前Node是链表,则在链表中插入或更新键值对

else {

//遍历以该Node为头结点的链表,判断该key是否已存在

for (int binCount = 0; ; ++binCount) {

//若该key不存在,则将key-value添加到Node数组中,这里采用尾插法

if ((e = p.next) == null) {

p.next = newNode(hash, key, value, null);

//链表长度 >= 桶的树化阈值=8,则将链表转换成红黑树

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;

}

}

//若该key已存在,则用新value替换旧value

if (e != null) { // existing mapping for key

V oldValue = e.value;

if (!onlyIfAbsent || oldValue == null)

e.value = value;

afterNodeAccess(e);

return oldValue;

}

}

++modCount;

// 插入成功后,判断实际存在的键值对数量size > 最大容量threshold

if (++size > threshold)

resize();

afterNodeInsertion(evict);

return null;

}

putTreeVal()

        //向红黑树插入或更新数据(键值对),遍历红黑树判断该节点的key是否与传入key相同,相同则新value覆盖旧value,不相同则插入

final TreeNode<K,V> putTreeVal(HashMap<K,V> map, Node<K,V>[] tab,

int h, K k, V v) {

Class<?> kc = null;

boolean searched = false;

TreeNode<K,V> root = (parent != null) ? root() : this;

for (TreeNode<K,V> p = root;;) {

int dir, ph; K pk;

if ((ph = p.hash) > h)

dir = -1;

else if (ph < h)

dir = 1;

else if ((pk = p.key) == k || (k != null && k.equals(pk)))

return p;

else if ((kc == null &&

(kc = comparableClassFor(k)) == null) ||

(dir = compareComparables(kc, k, pk)) == 0) {

if (!searched) {

TreeNode<K,V> q, ch;

searched = true;

if (((ch = p.left) != null &&

(q = ch.find(h, k, kc)) != null) ||

((ch = p.right) != null &&

(q = ch.find(h, k, kc)) != null))

return q;

}

dir = tieBreakOrder(k, pk);

}

TreeNode<K,V> xp = p;

if ((p = (dir <= 0) ? p.left : p.right) == null) {

Node<K,V> xpn = xp.next;

TreeNode<K,V> x = map.newTreeNode(h, k, v, xpn);

if (dir <= 0)

xp.left = x;

else

xp.right = x;

xp.next = x;

x.parent = x.prev = xp;

if (xpn != null)

((TreeNode<K,V>)xpn).prev = x;

moveRootToFront(tab, balanceInsertion(root, x));

return null;

}

}

}

resize()方法

    final Node<K,V>[] resize() {

Node<K,V>[] oldTab = table; //扩容前Node数组

int oldCap = (oldTab == null) ? 0 : oldTab.length; //扩容前Node数组长度

int oldThr = threshold; //扩容前Node数组阈值

int newCap, newThr = 0;

//Node数组长度大于0,非初始化数组

if (oldCap > 0) {

//扩容前Node数组容量超过最大值,不扩容

if (oldCap >= MAXIMUM_CAPACITY) {

threshold = Integer.MAX_VALUE;

return oldTab;

}

//没有超过最大值,数组长度扩容为原来的2倍

else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&

oldCap >= DEFAULT_INITIAL_CAPACITY)

newThr = oldThr << 1; // double threshold

}

//Node数组长度=0,初始化数组

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) {

// 遍历旧数组,重新计算每个Node在新数组的数组下标,使用尾插法将旧数组中的Node转移到新数组

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;

}

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;

//计算key存放Node数组中的数组下标,判断这个数组下标Node数组上是否有Node存在

if ((tab = table) != null && (n = tab.length) > 0 &&

(first = tab[(n - 1) & hash]) != null) {

//1.在Node数组中找key相等的Node

if (first.hash == hash && // always check first node

((k = first.key) == key || (key != null && key.equals(k))))

return first;

//2.在红黑树中找key相等的Node

if ((e = first.next) != null) {

if (first instanceof TreeNode)

return ((TreeNode<K,V>)first).getTreeNode(hash, key);

//3.在链表中找key相等的Node

do {

if (e.hash == hash &&

((k = e.key) == key || (key != null && key.equals(k))))

return e;

} while ((e = e.next) != null);

}

}

return null;

}

源码总结

1.JDK1.8的HashMap采用数组+单链表+红黑树的数据结构,数组和链表存储的是一个个Node对象,红黑树存储的是TreeNode对象
2.添加key-value时会根据key值计算出对应的hash值,再根据hash值计算出对应的数组下标,判断这个数组在这个下标中是否有Node存在:
若没有,则在该位置新建一个Node节点
若有则判断这个Node是属于链表还是属于红黑树,然后分别遍历链表或红黑树,判断是否有相同的key,如果有则用新value替换旧value,如果没有就将Node添加到链表或红黑树,注意这里的链表插入采用尾插法
3.在将Node插入到链表时:
会进行是否红黑树树化的判断,链表长度 >= 桶的树化阈值=8,则将链表转换成红黑树
会进行是否需要扩容的判断,当Node的数量,或者说key-value的数量大于扩容阈值 = 当前容量 x 加载因子,新建一个数组,容量时是数组的2倍,将旧entry数组上的entry数据转移到newtable中,让当前的数组指向新数组从而完成扩容。

4.hashmap1.8与hashmap1.7的区别:
1.数据结构不同
2.与1.7中hashmap的扩容机制不同:
a.hashmap1.8中的扩容后Node的位置是数组的原位置/原位置+旧容b.量,hashmap1.7则是原来位置
b.扩容时,hashmap1.8采用尾插法将数据转移到新数组中,hashmap1.7采用头插法

javahashmap集合

阅读 41更新于 今天 09:52

本作品系原创,采用《署名-非商业性使用-禁止演绎 4.0 国际》许可协议


我要去大厂

世界上最伟大的力量是坚持。

avatar

WillLiaowh

世界上最伟大的力量是坚持。

19 声望

5 粉丝

0 条评论

得票时间

avatar

WillLiaowh

世界上最伟大的力量是坚持。

19 声望

5 粉丝

宣传栏

数据结构

JDK1.8的HashMap采用数组+单链表+红黑树的数据结构,数组和链表存储的是一个个Node对象,红黑树存储的是TreeNode对象
【Java】JDK1.8 HashMap解析

Node

    static class Node<K,V> implements Map.Entry<K,V> {

final int hash;

final K key;

V value;

Node<K,V> next;

}

TreeNode

    static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {

TreeNode<K,V> parent; // red-black tree links

TreeNode<K,V> left;

TreeNode<K,V> right;

TreeNode<K,V> prev; // needed to unlink next upon deletion

boolean red;

TreeNode(int hash, K key, V val, Node<K,V> next) {

super(hash, key, val, next);

}

final TreeNode<K,V> root() {

for (TreeNode<K,V> r = this, p;;) {

if ((p = r.parent) == null)

return r;

r = p;

}

}

}

常用方法

常用API

V get(Object key); //获得指定key的值

V put(K key, V value); //添加key-value对

void putAll(Map<? extends K, ? extends V> m); //将指定Map中的key-value对复制到此Map中

V remove(Object key); //删除该key-value

boolean containsKey(Object key); //判断是否存在该key的key-value对;是则返回true

boolean containsValue(Object value); //判断是否存在该value的key-value对;是则返回true

Set<K> keySet(); //单独抽取key序列,将所有key生成一个Set

Collection<V> values(); //单独value序列,将所有value生成一个Collection

void clear(); // 清除HashMap中的所有key-value对

int size(); // 返回HashMap中所有key-value对的数量

boolean isEmpty(); // 判断HashMap是否为空,size == 0时表示为空

使用

public class HashMapTest {

public static void main(String[] args) {

/**

* 1. 声明1个 HashMap的对象

*/

Map<String, Integer> map = new HashMap<String, Integer>();

/**

* 2. 向HashMap添加数据(放入键-值对)

*/

map.put("Java", 1);

map.put("HashMap", 2);

map.put("List",3);

map.put("set",4);

/**

* 3. 获取 HashMap 的某个数据

*/

System.out.println("" + map.get("HashMap"));

/**

* 4. 遍历HashMap共有3种方法:分别针对Entry或key或value

* 步骤1:获得Entry或key或value的集合

* 步骤2:遍历,使用for循环或迭代器Iterator

*/

// 方法1:获得Entry的Set集合再遍历

// 获得Entry的Set集合

Set<Map.Entry<String, Integer>> entrySet = map.entrySet();

// 通过for循环遍历

for(Map.Entry<String, Integer> entry : entrySet){

System.out.print(entry.getKey());

System.out.println(entry.getValue());

}

// 通过迭代器遍历

// 先获得Entry的Iterator,再循环遍历

Iterator iter1 = entrySet.iterator();

while (iter1.hasNext()) {

// 遍历时,需先获取entry,再分别获取key、value

Map.Entry entry = (Map.Entry) iter1.next();

System.out.print((String) entry.getKey());

System.out.println((Integer) entry.getValue());

}

// 方法2:获得key的Set集合再遍历

Set<String> keySet = map.keySet();

// 通过for循环

for(String key : keySet){

System.out.print(key);

System.out.println(map.get(key));

}

// 通过迭代器遍历

// 先获得key的Iterator,再循环遍历

Iterator iter2 = keySet.iterator();

String key = null;

while (iter2.hasNext()) {

// 遍历时,需先获取key,再获取value

key = (String)iter2.next();

System.out.print(key);

System.out.println(map.get(key));

}

// 方法3:获得value的集合再遍历

Collection valueSet = map.values();

// 获得values的Iterator,再循环遍历

Iterator iter3 = valueSet.iterator();

while (iter3.hasNext()) {

System.out.println(iter3.next());

}

}

}

对于遍历方式,推荐使用针对 key-value对(Entry)的方式:效率高

  1. 对于遍历keySet,valueSet,实质上遍历了2次:
    第1次,for/iterator迭代器遍历;
    第2次 从HashMap中取出key的value操作
  2. 对于遍历entrySet,实质遍历了1次for/iterator迭代器遍历,Entry已经存储了key和 value

源码分析

主要属性

//默认容量

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;

//最大容量

static final int MAXIMUM_CAPACITY = 1 << 30;

//加载因子

static final float DEFAULT_LOAD_FACTOR = 0.75f;

//扩容阈值 = 容量 x 加载因子,当哈希表的大小 ≥ 扩容阈值时,就会扩容哈希表

int threshold

//存储数据的Node类型数组,长度=2的幂

transient Node<K,V>[] table;

//HashMap中存储的键值对的数量

transient int size

// 链表的树化阈值,即链表转成红黑树的阈值,当Node链表长度>该值时,则将链表转换成红黑树

static final int TREEIFY_THRESHOLD = 8;

// 链表的还原阈值,即红黑树转为链表的阈值,当在扩容时,HashMap的数据存储位置会重新计算,在重新计算存储位置后,当红黑树内TreeNode数量 < 6时,则将 红黑树转换成链表

static final int UNTREEIFY_THRESHOLD = 6;

// 最小链表树化容量阈值,即 当Node数组长度 > 该值时,才允许树形化链表,否则则直接扩容,而不是树形化

static final int MIN_TREEIFY_CAPACITY = 64;

构造方法

    //加载因子,容量可指定

public HashMap(int initialCapacity, float loadFactor) {

if (initialCapacity < 0)

throw new IllegalArgumentException("Illegal initial capacity: " +

initialCapacity);

if (initialCapacity > MAXIMUM_CAPACITY)

initialCapacity = MAXIMUM_CAPACITY;

if (loadFactor <= 0 || Float.isNaN(loadFactor))

throw new IllegalArgumentException("Illegal load factor: " +

loadFactor);

this.loadFactor = loadFactor;

this.threshold = tableSizeFor(initialCapacity);

}

//加载因子等于默认值,容量可指定

public HashMap(int initialCapacity) {

this(initialCapacity, DEFAULT_LOAD_FACTOR);

}

//默认构造函数,加载因子,容量等于默认值

public HashMap() {

this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted

}

//可传入一个map的构造函数

public HashMap(Map<? extends K, ? extends V> m) {

this.loadFactor = DEFAULT_LOAD_FACTOR;

putMapEntries(m, false);

}

put()方法

    public V put(K key, V value) {

return putVal(hash(key), key, value, false, true);

}

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,

boolean evict) {

Node<K,V>[] tab; Node<K,V> p; int n, i;

//1. 若Node数组为空,则通过resize()初始化数组

if ((tab = table) == null || (n = tab.length) == 0)

n = (tab = resize()).length;

//2.计算key存放Node数组中的数组下标,判断这个数组下标Node数组上是否有Node存在

//2.1若不存在,则在该位置新建一个Node节点

if ((p = tab[i = (n - 1) & hash]) == null)

tab[i] = newNode(hash, key, value, null)

//2.2若存在

else {

Node<K,V> e; K k;

//2.1.1判断key是否与数组上的Node里面的key是否相同,是则用新的value值替换旧的value值

if (p.hash == hash &&

((k = p.key) == key || (key != null && key.equals(k))))

e = p;

//2.1.2若不相同,判断当前Node是红黑树,则在树中插入或更新键值对

else if (p instanceof TreeNode)

e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);

//2.1.3若不相同,判断当前Node是链表,则在链表中插入或更新键值对

else {

//遍历以该Node为头结点的链表,判断该key是否已存在

for (int binCount = 0; ; ++binCount) {

//若该key不存在,则将key-value添加到Node数组中,这里采用尾插法

if ((e = p.next) == null) {

p.next = newNode(hash, key, value, null);

//链表长度 >= 桶的树化阈值=8,则将链表转换成红黑树

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;

}

}

//若该key已存在,则用新value替换旧value

if (e != null) { // existing mapping for key

V oldValue = e.value;

if (!onlyIfAbsent || oldValue == null)

e.value = value;

afterNodeAccess(e);

return oldValue;

}

}

++modCount;

// 插入成功后,判断实际存在的键值对数量size > 最大容量threshold

if (++size > threshold)

resize();

afterNodeInsertion(evict);

return null;

}

putTreeVal()

        //向红黑树插入或更新数据(键值对),遍历红黑树判断该节点的key是否与传入key相同,相同则新value覆盖旧value,不相同则插入

final TreeNode<K,V> putTreeVal(HashMap<K,V> map, Node<K,V>[] tab,

int h, K k, V v) {

Class<?> kc = null;

boolean searched = false;

TreeNode<K,V> root = (parent != null) ? root() : this;

for (TreeNode<K,V> p = root;;) {

int dir, ph; K pk;

if ((ph = p.hash) > h)

dir = -1;

else if (ph < h)

dir = 1;

else if ((pk = p.key) == k || (k != null && k.equals(pk)))

return p;

else if ((kc == null &&

(kc = comparableClassFor(k)) == null) ||

(dir = compareComparables(kc, k, pk)) == 0) {

if (!searched) {

TreeNode<K,V> q, ch;

searched = true;

if (((ch = p.left) != null &&

(q = ch.find(h, k, kc)) != null) ||

((ch = p.right) != null &&

(q = ch.find(h, k, kc)) != null))

return q;

}

dir = tieBreakOrder(k, pk);

}

TreeNode<K,V> xp = p;

if ((p = (dir <= 0) ? p.left : p.right) == null) {

Node<K,V> xpn = xp.next;

TreeNode<K,V> x = map.newTreeNode(h, k, v, xpn);

if (dir <= 0)

xp.left = x;

else

xp.right = x;

xp.next = x;

x.parent = x.prev = xp;

if (xpn != null)

((TreeNode<K,V>)xpn).prev = x;

moveRootToFront(tab, balanceInsertion(root, x));

return null;

}

}

}

resize()方法

    final Node<K,V>[] resize() {

Node<K,V>[] oldTab = table; //扩容前Node数组

int oldCap = (oldTab == null) ? 0 : oldTab.length; //扩容前Node数组长度

int oldThr = threshold; //扩容前Node数组阈值

int newCap, newThr = 0;

//Node数组长度大于0,非初始化数组

if (oldCap > 0) {

//扩容前Node数组容量超过最大值,不扩容

if (oldCap >= MAXIMUM_CAPACITY) {

threshold = Integer.MAX_VALUE;

return oldTab;

}

//没有超过最大值,数组长度扩容为原来的2倍

else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&

oldCap >= DEFAULT_INITIAL_CAPACITY)

newThr = oldThr << 1; // double threshold

}

//Node数组长度=0,初始化数组

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) {

// 遍历旧数组,重新计算每个Node在新数组的数组下标,使用尾插法将旧数组中的Node转移到新数组

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;

}

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;

//计算key存放Node数组中的数组下标,判断这个数组下标Node数组上是否有Node存在

if ((tab = table) != null && (n = tab.length) > 0 &&

(first = tab[(n - 1) & hash]) != null) {

//1.在Node数组中找key相等的Node

if (first.hash == hash && // always check first node

((k = first.key) == key || (key != null && key.equals(k))))

return first;

//2.在红黑树中找key相等的Node

if ((e = first.next) != null) {

if (first instanceof TreeNode)

return ((TreeNode<K,V>)first).getTreeNode(hash, key);

//3.在链表中找key相等的Node

do {

if (e.hash == hash &&

((k = e.key) == key || (key != null && key.equals(k))))

return e;

} while ((e = e.next) != null);

}

}

return null;

}

源码总结

1.JDK1.8的HashMap采用数组+单链表+红黑树的数据结构,数组和链表存储的是一个个Node对象,红黑树存储的是TreeNode对象
2.添加key-value时会根据key值计算出对应的hash值,再根据hash值计算出对应的数组下标,判断这个数组在这个下标中是否有Node存在:
若没有,则在该位置新建一个Node节点
若有则判断这个Node是属于链表还是属于红黑树,然后分别遍历链表或红黑树,判断是否有相同的key,如果有则用新value替换旧value,如果没有就将Node添加到链表或红黑树,注意这里的链表插入采用尾插法
3.在将Node插入到链表时:
会进行是否红黑树树化的判断,链表长度 >= 桶的树化阈值=8,则将链表转换成红黑树
会进行是否需要扩容的判断,当Node的数量,或者说key-value的数量大于扩容阈值 = 当前容量 x 加载因子,新建一个数组,容量时是数组的2倍,将旧entry数组上的entry数据转移到newtable中,让当前的数组指向新数组从而完成扩容。

4.hashmap1.8与hashmap1.7的区别:
1.数据结构不同
2.与1.7中hashmap的扩容机制不同:
a.hashmap1.8中的扩容后Node的位置是数组的原位置/原位置+旧容b.量,hashmap1.7则是原来位置
b.扩容时,hashmap1.8采用尾插法将数据转移到新数组中,hashmap1.7采用头插法

以上是 【Java】JDK1.8 HashMap解析 的全部内容, 来源链接: utcz.com/a/110876.html

回到顶部