说⼀下HashMap的Put⽅法

川长思鸟来 2024-02-05 22:41 16阅读 0赞

1、根据Key通过哈希算法与与运算得出数组下标

譬如：计算出键 张三 的索引位置  
//key.hashCode % 16

//table.lenth = \[0-15\]

1	static final int hash(Object key) {
        
    2	int h;
    3	return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    4	}

2、如果数组下标位置元素为空，则将key和value封装为Entry对象  
（JDK1.7中是Entry对象，JDK1.8中是Node对象）并放⼊该位置

2	static class Entry<K,V> implements Map.Entry<K,V>	{
        
    3	final K key;	
    4	V value;	
    5	Entry<K,V> next;	
    6	int hash;	
    7	....	
    8	}	
    9		
    10	//JDK1.8中是Node对象	
    11	Node<K,V> p = new Node<>(hash, key, value, next);

3、如果数组下标位置元素不为空，则要分情况讨论  
a. 如果是JDK1.7，则先判断是否需要扩容，如果要扩容就进⾏扩容，如果不⽤扩容就⽣成Entry对象，并使⽤头插法添加到当前位置的链表中  
b. 如果是JDK1.8，则先插⼊再扩容的，会先判断当前位置上的Node的类型，看是红⿊树Node，还是链表Node  
i. 如果是红⿊树Node，则是将key和value封装为⼀个红⿊树节点并添加到红⿊树中去，在这个过程中会判断红⿊树中是否存在当前key(equals⽅法来⽐较)，如果存在则更新value

ii. 如果此位置上的Node对象是链表节点，则将key和value封装为⼀个链表Node并通过尾插法插  
⼊到链表的最后位置去，因为是尾插法，所以需要遍历链表，在遍历链表的过程中会判断是否存在当前 key，如果存在则更新value，当遍历完链表后，将新链表Node插⼊到链表中，插⼊到链表后，会看当前链表的节点个数，如果⼤于等于8，链表中元素太多的时候会影响查找效率，所以当链表的元素个数达到8的时候使⽤链表存储就转变成了使⽤红⿊树存储  
iii. 将key和value封装为Node插⼊到链表或红⿊树中后，再判断是否需要进⾏扩容，如果需要就扩容，如果不需要就结束PUT⽅法  
![在这里插入图片描述][7c2766ac61d94237b0a692c99ff84f56.png]  
![在这里插入图片描述][a38a9245d7144388b814590148ad1a67.png]

[7c2766ac61d94237b0a692c99ff84f56.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/30/ef4033c91d68472687fbb1052b7a3e8f.png
[a38a9245d7144388b814590148ad1a67.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/30/e35e0994a2874400a4c51c259637952c.png