HashMap详解

客官°小女子只卖身不卖艺 2022-06-05 06:23 151阅读 0赞

Java集合框架强大、简单、易用。尤其在设计业务逻辑的编程中，集合框架可以说是使用最多的类。Map集合是一种把键（key）和值（value）的结构集合，在实际引用中及其广泛。本篇简单分析java中hashmap的实现，并简单分析它的一些性能，使用过程中的需要注意的地方。

# 1、HashMap 简介 #

*  HashMap 是一个Hash表（散列表），它存储的内容是键值对(key-value)映射。
 *  HashMap 继承于AbstractMap，实现了Map、Cloneable、java.io.Serializable接口。
 *  HashMap 的实现不是同步的，这意味着它不是线程安全的。它的key、value都可以为null。此外，HashMap中的映射不是有序的。

![70][]

# 2、数据结构 #

## 2.1 数据结构 ##

### 2.1.1  jdk 1.7版本数据结构 ###

jdk 1.7之前的版本 `HashMap` 采用的数据结构 = **数组（主） + 单链表（副）。**

**       **单链表主要是用来处理hash冲突，如果键值对key的hash值与数组中的hash值冲突，将原有的键值对移到链表中，冲突的键值对放在数组中。

![70 1][]

### 2.1.2  jdk 1.8 版本数据结构 ###

jdk 1.8之后的版本 `HashMap` 采用的数据结构 = **数组（主） + 单链表（副）+ 红黑树（副）。**

*  再链表的长度小于8时沿用之前版本使用单链表来解决hash值冲突。
 *  在链表的长度大于8时，使用红黑树来解决hash值冲突。

![70 2][]

红黑树简介：

![70 3][]

## 2.2 HashMap中的重要参数 ##

// 1. 容量（capacity）： HashMap中数组的长度
    // a. 容量范围：必须是2的幂 & <最大容量（2的30次方）
    // b. 初始容量 = 哈希表创建时的容量
      // 默认容量 = 16 = 1<<4 = 00001中的1向左移4位 = 10000 = 十进制的2^4=16
      static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
      // 最大容量 =  2的30次方（若传入的容量过大，将被最大值替换）
      static final int MAXIMUM_CAPACITY = 1 << 30;
    
    // 2. 加载因子(Load factor)：HashMap在其容量自动增加前可达到多满的一种尺度
    // a. 加载因子越大、填满的元素越多 = 空间利用率高、但冲突的机会加大、查找效率变低（因为链表变长了）
    // b. 加载因子越小、填满的元素越少 = 空间利用率小、冲突的机会减小、查找效率高（链表不长）
      // 实际加载因子
      final float loadFactor;
      // 默认加载因子 = 0.75
      static final float DEFAULT_LOAD_FACTOR = 0.75f;
    
    // 3. 扩容阈值（threshold）：当哈希表的大小 ≥ 扩容阈值时，就会扩容哈希表（即扩充HashMap的容量） 
    // a. 扩容 = 对哈希表进行resize操作（即重建内部数据结构），从而哈希表将具有大约两倍的桶数
    // b. 扩容阈值 = 容量 x 加载因子
      int threshold;
    
    // 4. 其他
     // 存储数据的Entry类型 数组，长度 = 2的幂
     // HashMap的实现方式 = 拉链法，Entry数组上的每个元素本质上是一个单向链表
      transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;  
     // HashMap的大小，即 HashMap中存储的键值对的数量
      transient int size;

![70 4][]

## 2.3 数据存储 ##

### 2.3.1 数据的存储流程 ###

![70 5][]

![70 6][]

## 2.4 数据结构的实现类 ##

### 2.3.1 Entry类 ###

在jdk 1.7 版本及之前`HashMap`中的数组元素 + 链表节点 采用 `Entry`类 实现

/** 
     * Entry类实现了Map.Entry接口
     * 即 实现了getKey()、getValue()、equals(Object o)和hashCode()等方法
    **/  
    static class Entry<K,V> implements Map.Entry<K,V> {
        final K key;  // 键
        V value;  // 值
        Entry<K,V> next; // 指向下一个节点 ，也是一个Entry对象，从而形成解决hash冲突的单链表
        int hash;  // hash值
    
        /** 
         * 构造方法，创建一个Entry 
         * 参数：哈希值h，键值k，值v、下一个节点n 
         */  
        Entry(int h, K k, V v, Entry<K,V> n) {  
            value = v;  
            next = n;  
            key = k;  
            hash = h;  
        }  
    
        // 返回 与 此项 对应的键
        public final K getKey() {  
            return key;  
        }  
    
        // 返回 与 此项 对应的值
        public final V getValue() {  
            return value;  
        }  
    
        public final V setValue(V newValue) {  
            V oldValue = value;  
            value = newValue;  
            return oldValue;  
        }  
    
       /** 
         * equals（）
         * 作用：判断2个Entry是否相等，必须key和value都相等，才返回true  
         */ 
          public final boolean equals(Object o) {  
            if (!(o instanceof Map.Entry))  
                return false;  
            Map.Entry e = (Map.Entry)o;  
            Object k1 = getKey();  
            Object k2 = e.getKey();  
            if (k1 == k2 || (k1 != null && k1.equals(k2))) {  
                Object v1 = getValue();  
                Object v2 = e.getValue();  
                if (v1 == v2 || (v1 != null && v1.equals(v2)))  
                    return true;  
            }  
            return false;  
        }  
    
        /** 
         * hashCode（） 
         */ 
        public final int hashCode() { 
            return Objects.hashCode(getKey()) ^ Objects.hashCode(getValue());  
        }  
    
        public final String toString() {  
            return getKey() + "=" + getValue();  
        }  
    
        /** 
         * 当向HashMap中添加元素时，即调用put(k,v)时， 
         * 对已经在HashMap中k位置进行v的覆盖时，会调用此方法 
         * 此处没做任何处理 
         */  
        void recordAccess(HashMap<K,V> m) {  
        }  
    
        /** 
         * 当从HashMap中删除了一个Entry时，会调用该函数 
         * 此处没做任何处理 
         */  
        void recordRemoval(HashMap<K,V> m) {  
        } 
    
    }

### 2.3.2  `Node`类 ###

`在jdk 1.8版本及之后HashMap`中的数组元素 + 链表节点 采用 `Node`类 实现

/** 
      * Node  = HashMap的内部类，实现了Map.Entry接口，本质是 = 一个映射(键值对)
      * 实现了getKey()、getValue()、equals(Object o)和hashCode()等方法
      **/  
      static class Node<K,V> implements Map.Entry<K,V> {
    
            final int hash; // 哈希值，HashMap根据该值确定记录的位置
            final K key; // key
            V value; // 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;
            }
    
            public final K getKey()        { return key; }   // 返回 与 此项 对应的键
            public final V getValue()      { return value; } // 返回 与 此项 对应的值
            public final String toString() { return key + "=" + value; }
    
            public final V setValue(V newValue) {
                V oldValue = value;
                value = newValue;
                return oldValue;
            }
    
          /** 
            * hashCode（） 
            */
            public final int hashCode() {
                return Objects.hashCode(key) ^ Objects.hashCode(value);
            }
    
          /** 
            * equals（）
            * 作用：判断2个Entry是否相等，必须key和value都相等，才返回true  
            */
            public final boolean equals(Object o) {
                if (o == this)
                    return true;
                if (o instanceof Map.Entry) {
                    Map.Entry<?,?> e = (Map.Entry<?,?>)o;
                    if (Objects.equals(key, e.getKey()) &&
                        Objects.equals(value, e.getValue()))
                        return true;
                }
                return false;
            }
        }

### 2.3.3 TreeNode类 ###

`在jdk 1.8版本中加入了红黑树，HashMap`中的红黑树节点 采用 `TreeNode` 类 实现

/**
      * 红黑树节点 实现类：继承自LinkedHashMap.Entry<K,V>类
      */
      static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {  
    
        // 属性 = 父节点、左子树、右子树、删除辅助节点 + 颜色
        TreeNode<K,V> parent;  
        TreeNode<K,V> left;   
        TreeNode<K,V> right;
        TreeNode<K,V> prev;   
        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;  
            }  
        }

# 3 HashMap的使用 #

## 3.1 主要方法API ##

V get(Object key); // 获得指定键的值
    V put(K key, V value);  // 添加键值对
    void putAll(Map<? extends K, ? extends V> m);  // 将指定Map中的键值对 复制到 此Map中
    V remove(Object key);  // 删除该键值对
    
    boolean containsKey(Object key); // 判断是否存在该键的键值对；是 则返回true
    boolean containsValue(Object value);  // 判断是否存在该值的键值对；是 则返回true
    
    Set<K> keySet();  // 单独抽取key序列，将所有key生成一个Set
    Collection<V> values();  // 单独value序列，将所有value生成一个Collection
    
    void clear(); // 清除哈希表中的所有键值对
    int size();  // 返回哈希表中所有 键值对的数量 = 数组中的键值对 + 链表中的键值对
    boolean isEmpty(); // 判断HashMap是否为空；size == 0时 表示为 空

## 3.2 使用示例 ##

public class HashMapTest {
        public static void main(String[] args) {
          /**
            * 1. 声明1个 HashMap的对象
            */
            Map<String, Integer> map = new HashMap<String, Integer>();
    
          /**
            * 2. 向HashMap添加数据（成对 放入 键 - 值对）
            */
            map.put("Android", 1);
            map.put("Java", 2);
            map.put("iOS", 3);
            map.put("数据挖掘", 4);
            map.put("产品经理", 5);
    
           /**
            * 3. 获取 HashMap 的某个数据
            */
            System.out.println("key = 产品经理时的值为：" + map.get("产品经理"));
    
          /**
            * 4. 获取 HashMap 的全部数据：遍历HashMap
            * 核心思想：
            * 步骤1：获得key-value对（Entry） 或 key 或 value的Set集合
            * 步骤2：遍历上述Set集合(使用for循环 、 迭代器（Iterator）均可)
            * 方法共有3种：分别针对 key-value对（Entry） 或 key 或 value
            */
    
            // 方法1：获得key-value的Set集合 再遍历
            System.out.println("方法1");
            // 1. 获得key-value对（Entry）的Set集合
            Set<Map.Entry<String, Integer>> entrySet = map.entrySet();
            // 2. 遍历Set集合，从而获取key-value
            // 2.1 通过for循环
            for(Map.Entry<String, Integer> entry : entrySet){
                System.out.print(entry.getKey());
                System.out.println(entry.getValue());
            }
    
            System.out.println("----------");
            // 2.2 通过迭代器：先获得key-value对（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集合 再遍历
            System.out.println("方法2");
    
            // 1. 获得key的Set集合
            Set<String> keySet = map.keySet();
    
            // 2. 遍历Set集合，从而获取key，再获取value
            // 2.1 通过for循环
            for(String key : keySet){
                System.out.print(key);
                System.out.println(map.get(key));
            }
    
            System.out.println("----------");
    
            // 2.2 通过迭代器：先获得key的Iterator，再循环遍历
            Iterator iter2 = keySet.iterator();
            String key = null;
            while (iter2.hasNext()) {
                key = (String)iter2.next();
                System.out.print(key);
                System.out.println(map.get(key));
            }
    
            // 方法3：获得value的Set集合 再遍历
            System.out.println("方法3");
    
            // 1. 获得value的Set集合
            Collection valueSet = map.values();
    
            // 2. 遍历Set集合，从而获取value
            // 2.1 获得values 的Iterator
            Iterator iter3 = valueSet.iterator();
            // 2.2 通过遍历，直接获取value
            while (iter3.hasNext()) {
                System.out.println(iter3.next());
            }
        }
    
    }

对于遍历方式，推荐使用针对 key-value对（Entry）的方式：效率高 。

**原因：**

*  对于 遍历keySet 、valueSet，实质上是遍历了2次：1、转为 iterator 迭代器遍历；2、从 HashMap 中取出 key 的 value 操作（通过 key 值 hashCode 和 equals 索引）
 *   对于 遍历 entrySet ，实质遍历了1次获取存储实体Entry（存储了key 和 value ）

[70]: /images/20220605/639440a0493b48ab9da4f371e1688126.png
[70 1]: /images/20220605/e36a26064a584efca8480c96eedb2b27.png
[70 2]: /images/20220605/5ec4356987be4f76a3fbbcfe95f74481.png
[70 3]: /images/20220605/0c6ff2cf8ca942b6872fec7fbd7b01ab.png
[70 4]: /images/20220605/22692a0029514ac69215e06bbb4763a5.png
[70 5]: /images/20220605/4c2af0cabf9e4ae3b8d2fcf7c8e55b56.png
[70 6]: /images/20220605/1852458b94804dbbb41d661d9a3a902d.png