HashMap是一种以key-value键值对为节点的数据集合
一、HashMap的使用
1.HashMap与其他集合数据结构的关系
(1)HashMap与其他集合的继承关系
(2)HashMap所包含的方法
2.HashMap遍历元素的方式
(1)通过遍历表的所有key，再通过key来获取值
- 适合场景：只需要获取表的key的情况
Map<Integer, String> userMap = new HashMap<Integer, String>(5);userMap.put(1, "诗心");userMap.put(2, "张三");userMap.put(3, "李四");//第1种：通过获取表所有的key来间接获得其对应的值，比较适合只取key的情况Set<Integer> userKeysSet = userMap.keySet();for (Integer key : userKeysSet) {String value = userMap.get(key);System.out.println(value);}
注：如果我们有N个元素，则需要N+1取操作才能遍历获取到所有的键和值(1次是所有key,N是遍历所有key并通过key来获取相应的value)
(2)直接获取表所有的值
- 适合场景：只需要获取表的所有的值的情况，不关心key
//第2种：通过获取所有的value,比较适合只需要获取value的情况(不需要查看key的情况)Collection<String> values = userMap.values();for (String val : values) {System.out.println(val);}
(3)获取所有节点(每个节点包含键和值)的集合
- 适合场景：需要获取所有key和value的情况(在资源无限制的情况下，一次读取到内存中)
//第3种：获取所有节点集合，适合需要key也需要获取value的情况Set<Map.Entry<Integer, String>> entrySet = userMap.entrySet();for (Map.Entry<Integer, String> entry : entrySet) {System.out.println(entry.getKey());System.out.println(entry.getValue());}
(4)通过节点迭代器来获取所有节点
- 适合场景：需要获取所有key和value的情况(在资源有限制的情况下，一次只读取一个节点)
//第4种：获取节点的迭代器，通过迭代器来遍历，适合既需要key也需要获取value的情况Iterator<Map.Entry<Integer, String>> userIterator = userMap.entrySet().iterator();while (userIterator.hasNext()) {Map.Entry<Integer, String> entry = userIterator.next();System.out.println(entry.getKey());System.out.println(entry.getValue());}
(5)通过forEach(jdk1.8及以上)方法来遍历
- 适合场景：在jdk1.8+环境，而且需要获取key和value的情况
//第5种:通过forEach方法(jdk1.8及以上新增)来遍历userMap.forEach((key, value)->{System.out.println(key);System.out.println(value);});
综上：可以根据自己项目中的使用场景选择相应的遍历方式，大多数据场景，建议优先选用第3-5这3种遍历方式，效率更高
3.HashMap实例化方法
- new HashMap():直接初始化
- new HashMap(int capacity):使用一个指定的容量来初始化，表示初始有capacity个节点
- new HashMap(int capacity, float loadFactor)
- capacity:初始化容量
- loadFactor:负载因子，表示当容量达到当前容量的一个比例时，hash表需要扩容，这个比例就是负载因子
- new HashMap(Map map):通过另外一个map对象进行初始化
//1.使用默认的容量进行初始化Map<Integer, String> defaultMap = new HashMap<Integer, String>();//2.通过指定初始容量来初始化Map<Integer, String> userMap = new HashMap<Integer, String>(5);//3.通过另外一个Map对象进行初始化Map<Integer, String> tMap = new TreeMap<Integer, String>();tMap.put(10, "JAVA");tMap.put(12, "C");Map<Integer, String> langMap = new HashMap<Integer, String>(tMap);System.out.println(langMap); //{12=C, 10=JAVA}
二、HashMap的实现原理解读
1.HashMap的实现
- JDK1.7及之前：数组+链表
- JDK1.8及之后：数组+链表+红黑树
- 根据hash算法对key进行hash运行，得出key存储的位置
- 查找存储位置上是否已经存储了值，如果已经存储了值，说明有hash冲突，使用链表的形式，在该位置上最后一个元素的next指针指向当前插入的元素
- 如果这个存储位置上链表的数量已经达到阀值(默认为8)，则通过红黑树的形式存储该位置上所有的节点值
2.HashMap的组成
整体：HashMap是有多个节点(Map.Node)组成的一个表结构
(1)HashMap的属性
- table : 存放节点的数组
- entrySet : 节点集合
- size : 节点长度
- loadFactor：负载因子，当当前容量达到初始容量的loadFactor这个比例时，表将进行扩容
- threshold：进行扩容的阀值
其他的默认值说明：
//默认初始化桶大小(默认容量:16)static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16//最大桶数量(最大容量，能存放多少个节点：2的30次方)static final int MAXIMUM_CAPACITY = 1 << 30;//默认的负载因子大小static final float DEFAULT_LOAD_FACTOR = 0.75f;//使用红黑树进行存储的阀值(当同一个桶存储大于8个节点时，采用红黑树进行存储)static final int TREEIFY_THRESHOLD = 8;//不使用红黑树进行存储的阀值(主要使用在扩容的时候)static final int UNTREEIFY_THRESHOLD = 6;//可以使用红黑树进行存储的最小表容量。static final int MIN_TREEIFY_CAPACITY = 64;
(2)HashMap的节点Node
它继承自Map.Entry
- key:节点的key
- value:节点的值
- hash:节点key计算出来的hash值，即为节点存储的位置索引
- next:指向下一个节点的指针
3.HashMap添加节点的方法put实现解读
- (1)通过hash函数将key值转化成当前key在表中存储的位置(索引)
- (2)通过索引位置找到表中的旧元素
- (2.1)如果旧元素不存在，即这个索引位置还没有存储任何值，直接通过当前的key和value生成新的节点，将新生成的节点存入到这个位置上
- (2.2)如果旧元素存在
- (2.2.1)如果旧元素的key和当前put的节点的key相等，那直接更新这个节点的值即可
- (2.2.2)如果旧元素节点是一个树节点(红黑树节点)，那么通过树的插入规则进行插入或替换
- (2.2.3)如果旧元素节点是一个链表节点，那么遍历链表，将节点插入到链表末尾，并且如果链表长度达到需要转化为红黑树的阀值，则将链表转化为红黑树
- (3)如果节点数达到需要扩容的阀值，则对整个表进行扩容
//插入或更新指定key的值public V put(K key, V value) {//通过调用putVal来实现return putVal(hash(key), key, value, false, true);}final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {/*1.定义需要使用的局部变量：(1)当前位置的节点集合tab(2)当前遍历节点指针p(3)当前位置计数n(4)数组索引i*/Node<K,V>[] tab; Node<K,V> p; int n, i;//2.如果表是空表，初始化或扩容并设置n和tab的值if ((tab = table) == null || (n = tab.length) == 0)n = (tab = resize()).length;//3.当前位置上没有存储其他值，那么这就是一个新的节点，直接放于当前位置即可if ((p = tab[i = (n - 1) & hash]) == null)tab[i] = newNode(hash, key, value, null);else {//e表示节点，k表示节点的keyNode<K,V> e; K k;//4.如果当前位置已经存储其他值//4.1如果插入的key已经存在，那么只需要更新值if (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k))))e = p;else if (p instanceof TreeNode)//4.2 如果插入的节点是一个树节点e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);else {//4.3 插入的节点的位置是一个链表//binCount为当前索引位置遍历节点计数器for (int binCount = 0; ; ++binCount) {//找到当前位置所存储的链表的最后一个元素(最后一个元素的next为null)if ((e = p.next) == null) {//插入到链表末尾p.next = newNode(hash, key, value, null);//如果当前位置上链表的个数达到需要红黑树存储的阀值，则将该位置上的节点存储转化为红黑树存储if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1sttreeifyBin(tab, hash);break;}if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))break;p = e;}}//通过hash值找到了相应的节点if (e != null) { // existing mapping for keyV oldValue = e.value;if (!onlyIfAbsent || oldValue == null)e.value = value;afterNodeAccess(e);return oldValue;}}++modCount;//5.如果节点数达到扩容的阀值，则进行扩容if (++size > threshold)resize();afterNodeInsertion(evict);return null;}
4.HashMap获取节点的方法get实现解读
- (1)将查找的key通过hash函数转化为表上的位置索引
- (2)通过位置索引查找节点
- (2.1) 如果表对应的位置上元素节点的key与查找的key相等，那么直接返回这个节点即可
- (2.2) 如果这个节点是一个树节点，寻么通过树查找方式进行查找
- (2.3) 如果这个节点是一个链表节点，遍历链接进行比较查找
- (3)如果查找到相应的节点，直接返回节点的值即可，没查找返回null
public V get(Object key) {Node<K,V> e;//1.先通过hash函数计算出key对应的位置//2.再通过位置查找对应的节点元素的值，具体是调用getNode方法来实现return (e = getNode(hash(key), key)) == null ? null : e.value;}//通过具体的位置和key值来查找元素节点final Node<K,V> getNode(int hash, Object key) {/*1.定义局部变量(1)tab:用来表示哈希表的数组(2)first:当前位置首节点(3)e:用于遍历的节点指针(4)n:数组的长度(5)k:临时key*/Node<K,V>[] tab; Node<K,V> first, e; int n; K k;/*2.为tab和n赋值,并判断表是非空表(1)tab:哈希表数组(2)n:数组长度(3)first:当前hash值所在的位置链表或树的第一个元素节点*/if ((tab = table) != null && (n = tab.length) > 0 &&(first = tab[(n - 1) & hash]) != null) {//3.如果第一个节点值的key与要查找的key值相等，那么第一个节点就是要查找的节点if (first.hash == hash && // always check first node((k = first.key) == key || (key != null && key.equals(k))))return first;//4.如果第一个节点的next指针不为null，那么从next指针开始查找if ((e = first.next) != null) {//4.1如果first节点是树节点，那么通过树的查找方法查找key对应的节点if (first instanceof TreeNode)return ((TreeNode<K,V>)first).getTreeNode(hash, key);//4.2否则通过链表的查找方式进行遍历查找do {if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))return e;} while ((e = e.next) != null);}}return null;}
5.HashMap删除节点的方法remove实现解读
- (1)将查找的key通过hash函数转化为表上的位置索引
- (2)通过位置索引查找要删除节点
- (2.1) 如果表对应的位置上元素节点的key与查找的key相等，那么直接返回这个节点即可
- (2.2) 如果这个节点是一个树节点，寻么通过树查找方式进行查找
- (2.3) 如果这个节点是一个链表节点，遍历链接进行比较查找
- (3)如果查找到相应的节点，进行删除节点操作
- (3.1) 如果删除的节点是一个树节点，那么通过红黑树节点删除方法来进行删除
- (3.2) 如果删除的节点为删除位置上的第一个节点，那么将删除节点的下一个节点存储到数组索引对应的位置上
- (3.3) 如果删除的节点不在删除位置上的第一个位置，那么将删除节点的上一个节点的next指针指向删除节点的next指针
- (4)节点数更新
public V remove(Object key) {Node<K,V> e;//通过removeNode来删除节点return (e = removeNode(hash(key), key, null, false, true)) == null ?null : e.value;}final Node<K,V> removeNode(int hash, Object key, Object value,boolean matchValue, boolean movable) {/*1.定义变量会初始化(1)tab:用来存放表的节点数组(2)p:用来遍历的节点指针(3)n:节点的个数(4)index:索引下标*/Node<K,V>[] tab; Node<K,V> p; int n, index;//2.如果节点表不是空表，而且hash值对应的位置上的元素不为nullif ((tab = table) != null && (n = tab.length) > 0 &&(p = tab[index = (n - 1) & hash]) != null) {Node<K,V> node = null, e; K k; V v;//2.1 如果索引位置上对应的节点的key与要删除的key是相等的，那么这个节点就是要删除的节点if (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k))))node = p;else if ((e = p.next) != null) {//2.2 如果这个位置上的节点是树节点，那么通过树查找方法获取key对应的树节点if (p instanceof TreeNode)node = ((TreeNode<K,V>)p).getTreeNode(hash, key);else {//2.3 如果这个位置上的节点是链表节点，通过遍历链表获取要查找的节点do {if (e.hash == hash &&((k = e.key) == key ||(key != null && key.equals(k)))) {node = e;break;}p = e;} while ((e = e.next) != null);}}//3.如果查找的节点存在if (node != null && (!matchValue || (v = node.value) == value ||(value != null && value.equals(v)))) {//3.1 如果删除的节点是树节点，那么通过树删除方法进行节点删除if (node instanceof TreeNode)((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);//3.2 如果删除的节点是存储位置的第一个节点，那么就将删除节点后面的那个节点存放到这个位置上else if (node == p)tab[index] = node.next;else//3.3 如果删除的节点不是存储位置上的第一个节点，那么将删除节点的前一个节点的next指针指向删除节点的next指针p.next = node.next;++modCount;//4.节点数更新--size;afterNodeRemoval(node);return node;}}return null;}