Java数据结构之HashMap的使用及实现原理解读

HashMap是一种以key-value键值对为节点的数据集合

一、HashMap的使用

1.HashMap与其他集合数据结构的关系
(1)HashMap与其他集合的继承关系

HashMap与其他集合数据结构的关系

(2)HashMap所包含的方法

HashMap实现的方法

2.HashMap遍历元素的方式
(1)通过遍历表的所有key,再通过key来获取值
  • 适合场景:只需要获取表的key的情况
  1. Map<Integer, String> userMap = new HashMap<Integer, String>(5);
  2. userMap.put(1, "诗心");
  3. userMap.put(2, "张三");
  4. userMap.put(3, "李四");
  5. //第1种:通过获取表所有的key来间接获得其对应的值,比较适合只取key的情况
  6. Set<Integer> userKeysSet = userMap.keySet();
  7. for (Integer key : userKeysSet) {
  8. String value = userMap.get(key);
  9. System.out.println(value);
  10. }

注:如果我们有N个元素,则需要N+1取操作才能遍历获取到所有的键和值(1次是所有key,N是遍历所有key并通过key来获取相应的value)

(2)直接获取表所有的值
  • 适合场景:只需要获取表的所有的值的情况,不关心key
  1. //第2种:通过获取所有的value,比较适合只需要获取value的情况(不需要查看key的情况)
  2. Collection<String> values = userMap.values();
  3. for (String val : values) {
  4. System.out.println(val);
  5. }
(3)获取所有节点(每个节点包含键和值)的集合
  • 适合场景:需要获取所有key和value的情况(在资源无限制的情况下,一次读取到内存中)
  1. //第3种:获取所有节点集合,适合需要key也需要获取value的情况
  2. Set<Map.Entry<Integer, String>> entrySet = userMap.entrySet();
  3. for (Map.Entry<Integer, String> entry : entrySet) {
  4. System.out.println(entry.getKey());
  5. System.out.println(entry.getValue());
  6. }
(4)通过节点迭代器来获取所有节点
  • 适合场景:需要获取所有key和value的情况(在资源有限制的情况下,一次只读取一个节点)
  1. //第4种:获取节点的迭代器,通过迭代器来遍历,适合既需要key也需要获取value的情况
  2. Iterator<Map.Entry<Integer, String>> userIterator = userMap.entrySet().iterator();
  3. while (userIterator.hasNext()) {
  4. Map.Entry<Integer, String> entry = userIterator.next();
  5. System.out.println(entry.getKey());
  6. System.out.println(entry.getValue());
  7. }
(5)通过forEach(jdk1.8及以上)方法来遍历
  • 适合场景:在jdk1.8+环境,而且需要获取key和value的情况
  1. //第5种:通过forEach方法(jdk1.8及以上新增)来遍历
  2. userMap.forEach((key, value)->{
  3. System.out.println(key);
  4. System.out.println(value);
  5. });

综上:可以根据自己项目中的使用场景选择相应的遍历方式,大多数据场景,建议优先选用第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. //1.使用默认的容量进行初始化
  2. Map<Integer, String> defaultMap = new HashMap<Integer, String>();
  3. //2.通过指定初始容量来初始化
  4. Map<Integer, String> userMap = new HashMap<Integer, String>(5);
  5. //3.通过另外一个Map对象进行初始化
  6. Map<Integer, String> tMap = new TreeMap<Integer, String>();
  7. tMap.put(10, "JAVA");
  8. tMap.put(12, "C");
  9. Map<Integer, String> langMap = new HashMap<Integer, String>(tMap);
  10. System.out.println(langMap); //{12=C, 10=JAVA}

二、HashMap的实现原理解读

1.HashMap的实现
  • JDK1.7及之前:数组+链表
  • JDK1.8及之后:数组+链表+红黑树
    • 根据hash算法对key进行hash运行,得出key存储的位置
    • 查找存储位置上是否已经存储了值,如果已经存储了值,说明有hash冲突,使用链表的形式,在该位置上最后一个元素的next指针指向当前插入的元素
    • 如果这个存储位置上链表的数量已经达到阀值(默认为8),则通过红黑树的形式存储该位置上所有的节点值

HashMap的实现原理

2.HashMap的组成

整体:HashMap是有多个节点(Map.Node)组成的一个表结构

(1)HashMap的属性
  • table : 存放节点的数组
  • entrySet : 节点集合
  • size : 节点长度
  • loadFactor:负载因子,当当前容量达到初始容量的loadFactor这个比例时,表将进行扩容
  • threshold:进行扩容的阀值

其他的默认值说明:

  1. //默认初始化桶大小(默认容量:16)
  2. static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
  3. //最大桶数量(最大容量,能存放多少个节点:2的30次方)
  4. static final int MAXIMUM_CAPACITY = 1 << 30;
  5. //默认的负载因子大小
  6. static final float DEFAULT_LOAD_FACTOR = 0.75f;
  7. //使用红黑树进行存储的阀值(当同一个桶存储大于8个节点时,采用红黑树进行存储)
  8. static final int TREEIFY_THRESHOLD = 8;
  9. //不使用红黑树进行存储的阀值(主要使用在扩容的时候)
  10. static final int UNTREEIFY_THRESHOLD = 6;
  11. //可以使用红黑树进行存储的最小表容量。
  12. 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)如果节点数达到需要扩容的阀值,则对整个表进行扩容
  1. //插入或更新指定key的值
  2. public V put(K key, V value) {
  3. //通过调用putVal来实现
  4. return putVal(hash(key), key, value, false, true);
  5. }
  6. final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
  7. boolean evict) {
  8. /*
  9. 1.定义需要使用的局部变量:
  10. (1)当前位置的节点集合tab
  11. (2)当前遍历节点指针p
  12. (3)当前位置计数n
  13. (4)数组索引i
  14. */
  15. Node<K,V>[] tab; Node<K,V> p; int n, i;
  16. //2.如果表是空表,初始化或扩容并设置n和tab的值
  17. if ((tab = table) == null || (n = tab.length) == 0)
  18. n = (tab = resize()).length;
  19. //3.当前位置上没有存储其他值,那么这就是一个新的节点,直接放于当前位置即可
  20. if ((p = tab[i = (n - 1) & hash]) == null)
  21. tab[i] = newNode(hash, key, value, null);
  22. else {
  23. //e表示节点,k表示节点的key
  24. Node<K,V> e; K k;
  25. //4.如果当前位置已经存储其他值
  26. //4.1如果插入的key已经存在,那么只需要更新值
  27. if (p.hash == hash &&
  28. ((k = p.key) == key || (key != null && key.equals(k))))
  29. e = p;
  30. else if (p instanceof TreeNode)
  31. //4.2 如果插入的节点是一个树节点
  32. e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
  33. else {
  34. //4.3 插入的节点的位置是一个链表
  35. //binCount为当前索引位置遍历节点计数器
  36. for (int binCount = 0; ; ++binCount) {
  37. //找到当前位置所存储的链表的最后一个元素(最后一个元素的next为null)
  38. if ((e = p.next) == null) {
  39. //插入到链表末尾
  40. p.next = newNode(hash, key, value, null);
  41. //如果当前位置上链表的个数达到需要红黑树存储的阀值,则将该位置上的节点存储转化为红黑树存储 
  42. if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
  43. treeifyBin(tab, hash);
  44. break;
  45. }
  46. if (e.hash == hash &&
  47. ((k = e.key) == key || (key != null && key.equals(k))))
  48. break;
  49. p = e;
  50. }
  51. }
  52. //通过hash值找到了相应的节点
  53. if (e != null) { // existing mapping for key
  54. V oldValue = e.value;
  55. if (!onlyIfAbsent || oldValue == null)
  56. e.value = value;
  57. afterNodeAccess(e);
  58. return oldValue;
  59. }
  60. }
  61. ++modCount;
  62. //5.如果节点数达到扩容的阀值,则进行扩容
  63. if (++size > threshold)
  64. resize();
  65. afterNodeInsertion(evict);
  66. return null;
  67. }
4.HashMap获取节点的方法get实现解读
  • (1)将查找的key通过hash函数转化为表上的位置索引
  • (2)通过位置索引查找节点
    • (2.1) 如果表对应的位置上元素节点的key与查找的key相等,那么直接返回这个节点即可
    • (2.2) 如果这个节点是一个树节点,寻么通过树查找方式进行查找
    • (2.3) 如果这个节点是一个链表节点,遍历链接进行比较查找
  • (3)如果查找到相应的节点,直接返回节点的值即可,没查找返回null
  1. public V get(Object key) {
  2. Node<K,V> e;
  3. //1.先通过hash函数计算出key对应的位置
  4. //2.再通过位置查找对应的节点元素的值,具体是调用getNode方法来实现
  5. return (e = getNode(hash(key), key)) == null ? null : e.value;
  6. }
  7. //通过具体的位置和key值来查找元素节点
  8. final Node<K,V> getNode(int hash, Object key) {
  9. /*1.定义局部变量
  10. (1)tab:用来表示哈希表的数组
  11. (2)first:当前位置首节点
  12. (3)e:用于遍历的节点指针
  13. (4)n:数组的长度
  14. (5)k:临时key
  15. */
  16. Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
  17. /*2.为tab和n赋值,并判断表是非空表
  18. (1)tab:哈希表数组
  19. (2)n:数组长度
  20. (3)first:当前hash值所在的位置链表或树的第一个元素节点
  21. */
  22. if ((tab = table) != null && (n = tab.length) > 0 &&
  23. (first = tab[(n - 1) & hash]) != null) {
  24. //3.如果第一个节点值的key与要查找的key值相等,那么第一个节点就是要查找的节点
  25. if (first.hash == hash && // always check first node
  26. ((k = first.key) == key || (key != null && key.equals(k))))
  27. return first;
  28. //4.如果第一个节点的next指针不为null,那么从next指针开始查找
  29. if ((e = first.next) != null) {
  30.    //4.1如果first节点是树节点,那么通过树的查找方法查找key对应的节点 
  31. if (first instanceof TreeNode)
  32. return ((TreeNode<K,V>)first).getTreeNode(hash, key);
  33. //4.2否则通过链表的查找方式进行遍历查找
  34. do {
  35. if (e.hash == hash &&
  36. ((k = e.key) == key || (key != null && key.equals(k))))
  37. return e;
  38. } while ((e = e.next) != null);
  39. }
  40. }
  41. return null;
  42. }
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)节点数更新
  1. public V remove(Object key) {
  2. Node<K,V> e;
  3. //通过removeNode来删除节点
  4. return (e = removeNode(hash(key), key, null, false, true)) == null ?
  5. null : e.value;
  6. }
  7. final Node<K,V> removeNode(int hash, Object key, Object value,
  8. boolean matchValue, boolean movable) {
  9. /*
  10. 1.定义变量会初始化
  11. (1)tab:用来存放表的节点数组
  12. (2)p:用来遍历的节点指针
  13. (3)n:节点的个数
  14. (4)index:索引下标
  15. */
  16. Node<K,V>[] tab; Node<K,V> p; int n, index;
  17. //2.如果节点表不是空表,而且hash值对应的位置上的元素不为null
  18. if ((tab = table) != null && (n = tab.length) > 0 &&
  19. (p = tab[index = (n - 1) & hash]) != null) {
  20. Node<K,V> node = null, e; K k; V v;
  21. //2.1 如果索引位置上对应的节点的key与要删除的key是相等的,那么这个节点就是要删除的节点
  22. if (p.hash == hash &&
  23. ((k = p.key) == key || (key != null && key.equals(k))))
  24. node = p;
  25. else if ((e = p.next) != null) {
  26. //2.2 如果这个位置上的节点是树节点,那么通过树查找方法获取key对应的树节点
  27. if (p instanceof TreeNode)
  28. node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
  29. else {
  30. //2.3 如果这个位置上的节点是链表节点,通过遍历链表获取要查找的节点
  31. do {
  32. if (e.hash == hash &&
  33. ((k = e.key) == key ||
  34. (key != null && key.equals(k)))) {
  35. node = e;
  36. break;
  37. }
  38. p = e;
  39. } while ((e = e.next) != null);
  40. }
  41. }
  42. //3.如果查找的节点存在
  43. if (node != null && (!matchValue || (v = node.value) == value ||
  44. (value != null && value.equals(v)))) {
  45. //3.1 如果删除的节点是树节点,那么通过树删除方法进行节点删除
  46. if (node instanceof TreeNode)
  47. ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
  48. //3.2 如果删除的节点是存储位置的第一个节点,那么就将删除节点后面的那个节点存放到这个位置上
  49. else if (node == p)
  50. tab[index] = node.next;
  51. else
  52. //3.3 如果删除的节点不是存储位置上的第一个节点,那么将删除节点的前一个节点的next指针指向删除节点的next指针
  53. p.next = node.next;
  54. ++modCount;
  55. //4.节点数更新
  56. --size;
  57. afterNodeRemoval(node);
  58. return node;
  59. }
  60. }
  61. return null;
  62. }