hashMap —— jdk1.7版本

• • 1. hashmap实现的接口
  • 2. hashmap的内部类分析
  • 3.hashmap 中的四个重要的实例变量
  • 3. hashmap内部中重要的默认属性
  • 4.重要方法
  • • 4.1构造方法
    • 4.2 put（K,V）
    • 4.2 get（）
    • 4.3 删除操作
    • 4.4扩容
  • 5. 小结

hashmap的使用比较简单，就不记了，这里直接分析hashmap的内部结构

1. hashmap实现的接口

这是map接口中的一些方法，包括了常见的get（），put（），remove（），contain（）等等。
观察map可以发现一个特别的方法keySet（），返回的是map中key的set集合，从这里可以知道在map中为了保证key的唯一性，这里使用的一个set集合来保存所有的key。

再来看看hashmap中的该方法的实现

hashmap中是自定义了一个内部类keySet继承了set集合类，方法keySet返回的set就是自定义的类得到。

2. hashmap的内部类分析

这里介绍几个重要的内部类

• Entry
  
  可以看到这个类实现了Map.Entry接口，接口中就是一些操作map常用的方法。可以看到在这个类中包含了一个next实例变量，可以知道这这是一个包含了kv的链表结构的类，hash 就是哈希值
  到这里可以知道，在hashmap中的所有的键值对都是保存在不同的一个Entry类中，然后如果通过hash值计算出来的槽位，如果槽位相同，那么这些类会被放在同一条单链表中。
• 迭代器
  
  可以看到在hashmap内部还提供了四个迭代器，关于迭代器需要知道的就是，迭代器的作用就是封装了不同数据结构的集合类，对外提供了一个同一的操作方式的一个内部类，比如遍历，删除等。在某些集合中，使用迭代器来遍历的话，效率会有质的提升。
  这里举个例子，比如遍历LinkedList，使用迭代器遍历，效率会比使用get（）的方式效率高很多。具体测试结果如下

使用get（）方式遍历

使用迭代器方式遍历

可以看到，遍历的效率提升了一倍，如果遍历的数据量更多，提升的效率会更多，有兴趣的朋友可以自己测试一下。

3.hashmap 中的四个重要的实例变量

    /**
     * The table, resized as necessary. Length MUST Always be a power of two.
     */ 
     —— 这是哈希表或哈希槽
    transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;

    /**
     * The number of key-value mappings contained in this map.
     */
     —— 哈希槽中实际的Entry的数量
    transient int size;

    /**
     * The next size value at which to resize (capacity * load factor).
     * @serial
     */
    // If table == EMPTY_TABLE then this is the initial capacity at which the
    // table will be created when inflated.
    —— 容量阙值 ， 用于扩容判断的依据 
    int threshold;
    /**
     * The load factor for the hash table.
     *
     * @serial
     */
     —— 负载因子 —— 默认为 0.75
    final float loadFactor;

3. hashmap内部中重要的默认属性

   /**
     * The default initial capacity - MUST be a power of two.
     */
     —— 默认哈希槽的大小为16
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

    /**
     * The maximum capacity, used if a higher value is implicitly specified
     * by either of the constructors with arguments.
     * MUST be a power of two <= 1<<30.
     */
     ——哈希槽最大大小 
    static final int MAXIMUM_CAPACITY = 1 << 30;

    /**
     * The load factor used when none specified in constructor.
     */
     —— 负载因子默认值
    static final float DEFAULT_LOAD_FACTOR = 0.75f;

4.重要方法

4.1构造方法

一共有四个构造方法

• 容量 + 负载因子
• 容量
• 默认
• 集合类
  
  这里主要介绍一下默认的构造方法
  
  传递了默认的容量和默认的负载因子调用另一个构造方法
  
  可以看到在构造方法中基本没做什么，就是做了一些容量的判断，和赋值,注意这里负载因子的值被赋值为了哈希表的大小（在计算哈希表真实的容量的时候会使用）此时哈希表依然是一个空表。特别注意： 这里的初始化容量并不是最终得容量大小，真实得大小会在进行put操作时计算，
  接下里就看看put方法

4.2 put（K,V）

    public V put(K key, V value) {
    // 判断哈希表是否是空表，就进行初始化，并重新计算哈希表得大小（重点）
        if (table == EMPTY_TABLE) {
            inflateTable(threshold);
        }
        // key为怒时，就会将该key存储在下标为0得哈希表中 —— 专门用于保存key为null的Entry
        if (key == null)
            return putForNullKey(value);
            // 计算hash值（重点）
        int hash = hash(key);
        // 计算 该哈希值对应的槽位值
        int i = indexFor(hash, table.length);
        // 遍历该槽位对应的单链表，查看是否存在相同的key
        for (Entry<K,V> e = table[i]; e != null; e = e.next) {
            Object k;
            //细节： 这里是先判断的hash值，在使用equals（）方法判断，因为 == 比较的效率比equeal（）方法 高。 提高执行效率
            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
            // 找到相同的key，就修改对应value的值然后返回oldkey
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;
            }
        }
        // modCount 记录的是对哈希表的操作的次数，包括 删除，修改，添加，主要是用在使用迭代器遍历的过程中防止在遍历过程中键值对被修改。
        modCount++;
        // 插入新的entry 到哈希表中 —— 使用的是头查法（重要）
        addEntry(hash, key, value, i);
        return null;
    }

上述过程中几个重要的方法
哈希值的计算hash（）

可以看到这里在使用hashCode（）计算得到了一个哈希值之后，又进行了一些列的位移，异或操作，主要就是为了是是计算得到的哈希值更加随机和均匀。提高get（）的效率
初始化哈希表容量的计算

关键点： 计算得到的哈希表的容量为： 大于等于设置的初始胡容量（或者默认）的最小的2的被数。比如 如果容量设置为 10， 那么初始化就是16，如果容量设置为20，那么初始化就是32。关于为什么要这样做，主要就是为了在后面计算槽位时，直接使用&（逻辑与）操作得到，获得更好的效率。
哈希表槽位的计算

头插法插入数据

插入的逻辑在createEntry中实现

4.2 get（）

针对key是否为null使用不同的获取方法，这里主要介绍不为null的情况，本质上是没有什么不同的，只是如果为null，那么就直接在0号槽位中查找。

思路： 就是通过key计算hash值，通过hash值计算得到槽位，然后遍历该槽位对应的单链表，比较key，然后返回

4.3 删除操作

思路： 类似的计算得到槽位id，然后遍历该槽位对应的单链表，拿到pre和next，删除entry

最后看一下扩容

4.4扩容

扩容主要是在需要存入新的entry时，才会判断是否扩容，并且一次扩容为之前的2倍。实现逻辑

这里主要做了就是拿到newCapacity，创建一个新的哈希表，然后调用transfer（）将旧表中的entry放置到新的哈希表中。
transfer（）方法

仔细观察这里，可以发现时这里使用的依然是头插法
过程描述：
就是遍历旧的哈希表，遍历每个槽位的单链表，然乎计算每一个entry在新的哈希表中的槽位，然后使用头插法插入。
rehash 判断，就是将得到的哈希值在进行一个hash计算，主要用于使新的哈希表中的entry更加的均匀。

扩容时的问题分析：
可以看到在整个扩容的过程中是没有使用任何的措施来保证线程的安全的，意思就是说整个扩容的过程中，多个线程是可以并发执行的，并且由于这里在扩容时，使用的依然是头插法，就会导致扩容后在某个槽位中出现循环链子，就会导致在后序某次get（）中出现死循环。
关于出现循环链有很多种情况，这里就不分析了，具体的可以找个视频看一下。

5. 小结

1.hashmap内部实现了map接口，可以很方便的按照键值存取，内部使用了数组链表和哈希的方式进行实现。决定了它有几个特点，保存和获取的效率都特别高，哈希值是随机的，所以哈希表中的键值对是没有顺序的。
2.hashmap不是线程安全的，与hashmap类似的还有一个类，hashtable，两者的原理基本一致，但是后者使用了synchronized 来保证了容器的线程安全性，但是其在加锁时使用的是整个表对象锁，效率比较低。分析可以知道，出现死锁的原因就是不同线程在扩容时同时操作同一个槽位的单链表，导致出现循环链，但是这里直接将锁加在了整个哈希表上，所以是不大合适的，所以在CurrentHashMap中使用的就是另一种加锁方式，来提高并发效率。