HashMap小结

1. HashMap基本特点2. HashMap实现方法3.Hash的底层实现

3.1 底层数据结构3.2 jdk1.8之前HashMap存在的问题3.3 Hash包含的重要变量 4.put方法分析5.常见问题

5.1加载因子为什么默认值为0.75f？5.2HashMap如何实现序列化和反序列化（io）5.3 HashMap和Hashtable的区别5.4 HashMap和ConcurrentHashMap区别5.5 HashMap 的长度为什么是 2 的幂次方5.6 如何决定使用HashMap还是TreeMap?

1. HashMap基本特点

HashMap实现了Map接口。HashMap允许有null键和null值。HashMap键不能重复，null键会按照普通键对待。如果键重复，会按照覆盖重复的键。HashMap是无序的。Map接口提供三种collection视图，允许以键集，值集或者键-值映射关系集的形式查看某个映射的内容。映射的顺序定于迭代器在映射的collection视图上返回其元素的顺序。某些映射实现可明确保证其顺序，如TreeMap类。另一些映射实现则不保证顺序，如HashMap。 2. HashMap实现方法

方法	说明
Object put(Object key,Object value)	将互相关联的一组键/值对放入该映像
Object remove(Object key)	从映射中删除与key相关的映射
void clear()	从映像中删除所有映射
Object get(Object key)	获得与关键字key相关的值
boolean containsKey(Object Key)	判断映像中是否存在关键字key
int size()	返回当前映像中映射的数量
boolean isEmpty()	判断映像是否为空
Set keySet()	返回映像中所有关键字的视图集
Collection values()	返回映像中所有值的视图集
Set entrySet()	返回Map.Entry对象的视图集，即印象中的关键字/值对

3.Hash的底层实现

基于哈希表的Map接口实现。此实现提供所有可选的映射操作，并允许使用null值和null键。（除了非同步和允许使用的null之外，HashMap类与HashTable大致相同。）此类不保证映射的顺序，特别是它不保证该顺序恒久不变。

3.1 底层数据结构

HashMap底层采用哈希表结构（数组+链表+红黑树）实现，结合了数组和链表的优点：
1、数组优点：通过数组下标可以快速实现对数组元素的访问，效率极高。
2、链表优点：插入或删除数据不需要移动元素，只需要修改节点引用，效率极高。

HashMap内部使用数组存储数据，数组中的每个元素类型为Node

static class Node implements Map.Entry {
        final int hash;
        final K key;
        V value;
        Node next;

        Node(int hash, K key, V value, Node 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 int hashCode() {
            return Objects.hashCode(key) ^ Objects.hashCode(value);
        }

        public final V setValue(V newValue) {
            V oldValue = value;
            value = newValue;
            return oldValue;
        }

        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;
        }
    }

Node包含了四个字段：hash，key,value,next,其中next表示链表的下一个节点。

3.2 jdk1.8之前HashMap存在的问题

HashMap通过Hash方法计算key的哈希码，然后通过（n-1）&hash公式（n为数组长度）得到key在数组中存放的下标。当两个key在数组中存放的下标一致时，数组将以链表的方式存储（哈希碰撞）。在链表中查找数据必须从第一个元素开始一层一层往下找，知道找到为止，所以当链表长度越来越长时，HashMap的效率越来越低。

解决思想：
加入红黑树的结构来实现HashMap。当链表中的元素超过8个，并且数组长度大于64时，会将链表转换为红黑树。
红黑树的节点使用TreeNode表示：

static final class TreeNode extends linkedHashMap.Entry {
        TreeNode parent;  // red-black tree links
        TreeNode left;
        TreeNode right;
        TreeNode prev;    // needed to unlink next upon deletion
        boolean red;
        TreeNode(int hash, K key, V val, Node next) {
            super(hash, key, val, next);
        }
        .....
    }

3.3 Hash包含的重要变量

//默认数组初始化长度为16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
//数组最大容量，2的30次幂，即1073741824
 static final int MAXIMUM_CAPACITY = 1 << 30;
 //默认加载因子
 static final float DEFAULT_LOAD_FACTOR = 0.75f;
 //链表转换为红黑树的长度阈值
 static final int TREEIFY_THRESHOLD = 8;
 //红黑树转换为链表的长度阈值
 static final int UNTREEIFY_THRESHOLD = 6;
 //链表转换为红黑树时，数组容量必须大于等于64
  static final int MIN_TREEIFY_CAPACITY = 64;
  //HashMap里键值对的个数
  transient int size;
  //扩容阈值：数组容量*加载因子
  int threshold;
  //HashMap使用数组存放数据，数组元素类型为Node
  transient Node[] table;
  //加载因子
  final float loadFactor;

4.put方法分析

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node[] tab; Node p; int n, i;
        //如果数组为null或者长度为0，则进行数组初始化操作
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        //根据key的哈希值计算出数据插入数组的下标·位置
        if ((p = tab[i = (n - 1) & hash]) == null)
        //如果改下标还没有元素，则直接创建Node对象，并插入
            tab[i] = newNode(hash, key, value, null);
        else {
            Node e; K k;
            //如果目标位置key已经存在，则直接覆盖
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            //如果目标位置key不存在，且节点为红黑树，则插入红黑树中
            else if (p instanceof TreeNode)
                e = ((TreeNode)p).putTreeval(this, tab, hash, key, value);
            else {
            	//否则为链表结构，遍历链表，尾部插入
                for (int binCount = 0; ; ++binCount) {
                    if ((e = p.next) == null) {
                        p.next = newNode(hash, key, value, null);
                        //如果链表长度大于等于8，则考虑转换为红黑树
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash);//转换为红黑树操作，内部还会判断数组长度是否小于64，如果是的化不转换
                        break;
                    }
                    //如果链表中已经存在该key的话，直接覆盖替换
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;
                }
            }
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        ++modCount;
        //当键值对个数大于扩容阈值时，进行扩容操作
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;
    }

put操作过程总结：
1.判断HashMap数组是否为空，是的话初始化数组（由此可见，在创建HashMap对象时，不会直接初始化数组）
2.通过（n-1）&hash计算key在数组中的存放索引
3.如果目标索引为空的话，则创建node对象存储
4.如果目标索引不为空，则分为下面3中情况
（1）key值相同，则覆盖原索引
（2）该节点时红黑树的话，执行红黑树插入操作
（3）该节点类型是链表的话，遍历到最后一个元素尾部插入，如果中间遇到key相同的，则直接覆盖。如果链表长度大于等于8，数组长度大于等于64，则将链表转换为红黑树结构。
5.判断HashMap元素个数是否大于threshold（数组容量*加载因子），是的话，进行扩容操作（扩大2倍）

5.常见问题 5.1加载因子为什么默认值为0.75f？

扩容这个过程非常耗时，会影响程序性能。所以加载因子是基于容量和性能之间平衡的结果。
当加载因子过大时，扩容的占用就回贬低，但是哈希碰撞的几率增加，效率下降。
当加载因子过小时，容量占用变大。

5.2HashMap如何实现序列化和反序列化（io）

用于存储数据的table字段都使用transient修饰，通过transient修饰的字段在序列化时将被排除在外，那么HashMap在序列化后进行反序列化时，通过自定义方法来序列化和反序列化操作。
1.table一般不会存满，序列化table未使用的部分浪费时间和空间
2.同一个记住你支队在不同jvm下，在table存储的位置可能不同，那么反序列化时可能出错

5.3 HashMap和Hashtable的区别

同：HashMap 和 HashTable 都是基于哈希表实现的，其内部每个元素都是 key-value 键值对，HashMap 和 HashTable 都实现了 Map、Cloneable、Serializable 接口。
不同：
1.父类不同：HashMap 继承了 AbstractMap 类，而 HashTable 继承了 Dictionary 类。
2.空值不同：HashMap 允许空的 key 和 value 值，HashTable 不允许空的 key 和 value 值。HashMap 会把 Null key 当做普通的 key 对待。不允许 null key 重复。
3.安全性：HashMap线程不安全，HashTable线程安全。
4.性能：HashTable由于加了 synchronized 锁，操作较为耗时。
5.初始容量不同：HashTable 的初始长度是11，之后每次扩充容量变为之前的 2n+1(n为上一次的长度)，而 HashMap 的初始长度为16，之后每次扩充变为原来的两倍。创建时，如果给定了容量初始值，那么HashTable 会直接使用你给定的大小，而 HashMap 会将其扩充为2的幂次方大小。

5.4 HashMap和ConcurrentHashMap区别

HashMap线程不安全，ConcurrentHashMap是线程安全的。

5.5 HashMap 的长度为什么是 2 的幂次方

当数组长度不为2 的幂次方时，hash&（n-1）时，会产生大量重复数据，这样会增大 HashMap 碰撞的几率。

5.6 如何决定使用HashMap还是TreeMap?

如果你需要得到一个有序的结果时就应该使用TreeMap（因为HashMap中元素的排列顺序是不固定的）。除此之外，由于HashMap有更好的性能，所以大多不需要排序的时候我们会使用HashMap。

HashMap小结

Java相关栏目本月热门文章