HashMap如何添加元素详解

编程入门行业动态更新时间:2024-10-09 09:15:04

HashMap如何添加元素<a href=https://www.elefans.com/category/jswz/34/1770044.html style= 详解"/>

HashMap如何添加元素详解

Map接口结构

map接口是一个双边队列，拥有key,value两个属性，其中key在存储的集合中不允许重复，value可以重复。

`HashMap`特点

存储结构在jdk1.7当中是数组加链表的结构，在jdk1.8当中改为了数组加链表加红黑树的结构。
HashMap在多线程的环境下是不安全的，没有进行加锁措施，所以执行效率快。如果我么需要有一个线程安全的HashMap，可以使用Collections.synchronizedMap(Map<K,V> m)方法获得线程安全的HashMap，也可以使用ConcurrentHashMap类创建线程安全的map。
存储的元素在jdk1.7当中是Entry作为存储的节点，在jdk1.8当中用Node作为存储的节点，Node实现了Map.Entry接口。在map中其实是将key和value节点组合起来成为一个Node节点作为存储。

// jdk1.8Node节点
static class Node<K,V> implements Map.Entry<K,V> {final int hash;final K key;V value;Node<K,V> next;Node(int hash, K key, V value, Node<K,V> next) {this.hash = hash;this.key = key;this.value = value;this.next = next;}// 下面省略代码}

在HashMap中key不允许重复，value可以允许重复，并且key和value都允许是null值，因为他们是另外存储的。
当我们使用自定义类作为HashMap的key时我们需要重写object类的，hashCode()和equals()方法。
在HashMap中链表部分在jdk1.7中新的节点总是在链表的头部，旧的节点在新节点的next域当中，而在jdk1.8中是新的节点总是在链表的尾部，他们的指向都是由旧节点指向新的节点，由此我们可以记成七上八下。

`HashMap`当中常见的名词

DEFAULT_INITIAL_CAPACITY 默认数组容量大小，16
MAXIMUM_CAPACITY 最大数组容量大小，2^30
DEFAULT_LOAD_FACTOR 默认的负载因子，0.75
TREEIFY_THRESHOLD 链表改成红黑树存储的最小长度
MIN_TREEIFY_CAPACITY 链表改成红黑树存储，map数组最小容量

`HashMap`存储元素过程源码解析（jdk1.8）

// 存储元素的数组，加上transient关键字代表不可以被序列化transient Node<K,V>[] table;// 这个方法是HashMap对外公开的添加元素方法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;// 在jdk1.7当中，创建一个HashMap实例是直接分配一个长度为16的数组，// 在jdk1.8当中，创建HashMap时是分配了一个长度为0的数组，然后调用put方法时，如果数组长// 度为0时，则调用数组扩容方法，扩容数组到长度为16。当长度不为0时，扩容操作是扩大到原来// 长度的两倍if ((tab = table) == null || (n = tab.length) == 0)// 调用扩容方法，并利用n变量，记录数组的长度n = (tab = resize()).length;// 通过计算哈希散列，得出该key应该放在数组的哪一个位置上，用变量p存储该位置上的元素// 判断该位置上是否已经存在元素，如果不存在元素则直接将该元素放入数组中，存放if ((p = tab[i = (n - 1) & hash]) == null)tab[i] = newNode(hash, key, value, null);// 如果数组的该位置已经存在了元素else {Node<K,V> e; K k;// 比较需要加入的元素，于原来的元素hash值进行比较，如果hash值和equals都为true那么// 判定两个元素为相同元素，用变量e来记录原来的元素，方便下面进行替换if (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k))))e = p;// 如果上述条件不满足，但是是一个TreeNode类型，则当作树节点插入else if (p instanceof TreeNode)e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);else {// 当hash值不同，或者equals为false，也不是TreeNode时将新元素插入数组对应位置的// 链表中，遍历对应数组位置的链表for (int binCount = 0; ; ++binCount) {// 用变量e存储链表的下一个节点if ((e = p.next) == null) {// 如果该链表只有一个元素，则直接将旧节点的next域指向新的节点p.next = newNode(hash, key, value, null);// 当单条链表上元素数量大于最大数量时则按照红黑树存储8，在进行红黑树时// 又会进行判断数组容量是否到达红黑树最小容量64，两个条件同时满足，则该// 条链表改造成红黑树存储if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1sttreeifyBin(tab, hash);break;}// 比较链表的下一个节点的hash值和equalsif (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))break;p = e;}}// 如果e不等于null则证明，在链表中存在相同的元素，则进行替换if (e != null) { // existing mapping for keyV oldValue = e.value;if (!onlyIfAbsent || oldValue == null)e.value = value;afterNodeAccess(e);return oldValue;}}++modCount;if (++size > threshold)resize();afterNodeInsertion(evict);return null;}// 将链表改造成红黑树final void treeifyBin(Node<K,V>[] tab, int hash) {int n, index; Node<K,V> e;// 判断是否满足条件，数组大小达到64，没有达到则做扩容操作，达到则改成红黑树if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)resize();else if ((e = tab[index = (n - 1) & hash]) != null) {TreeNode<K,V> hd = null, tl = null;do {TreeNode<K,V> p = replacementTreeNode(e, null);if (tl == null)hd = p;else {p.prev = tl;tl.next = p;}tl = p;} while ((e = e.next) != null);if ((tab[index] = hd) != null)hd.treeify(tab);}}