紧接这上一篇：HashMap源码笔记（一）
我们继续来分析HashMap源码，接下来我们来看看HashMap的源码说明部分

image

HashMap通常被用做以binned为基础的哈希表，也就是链表，当bins容量过大时，它会转变成TreeNodes,类似于TreeMap,大多数方法使用简单的bins，但当需要使用时，会转变成TreeNode。

也就是说jdk1.8对哈希碰撞后的拉链算法进行了优化，当entry数量太多时，将链表重构为红黑树

image

注意： 哈希碰撞后的链表上达到8个节点时要将链表重构为红黑树

链表的原理及使用方式，可以查看《数据结构与算法》链表

突然感觉HashMap好难理解

image

put方法

大概思路

1. 对key的hashCode()做hash,然后在计算index
2. 如果没碰撞直接放到bucket里
3. 如果碰撞了，以链表的形式存在bucket里
4. 如果碰撞导致链表过长（大于等于TREEIFY_THRESHOLD也就是8），就把链表转换成红黑二叉树
5. 如果节点已经存在就替换old value ，保证key唯一性

6. 如果bucket满了(超过load factor*current capacity)，就要resize。

   
   image.png

/**
     * Implements Map.put and related methods
     *
     * @param hash hash for key
     * @param key the key
     * @param value the value to put
     * @param onlyIfAbsent if true, don't change existing value
     * @param evict if false, the table is in creation mode.
     * @return previous value, or null if none
     */
    final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        else {
            Node<K,V> e; K k;
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            else if (p instanceof TreeNode)
                e = ((TreeNode<K,V>)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);
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash);
                        break;
                    }
                    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;
    }

我们先来理解hashCode及HashMap中的hash函数

hash表也称为散列表，是根据（key,value）进行直接访问的数据结构，也就是说，它通过（key,value）映射到表中的一个位置来访问记录，以加快查找的速度，这个映射函数叫做散列函数，这个表叫做散列表。

给定表M,存在函数f(key) 对任意的关键值key，代入函数后若能的到包含关键字的记录在表中的地址，则称M为哈希表，函数f(key)为Hash函数。

简单理解就是在记录的存储位置和它的关键字之间建立了一个对应的关系f,使每个关键字和结构中一个唯一的存储位置对应。

具有快速查找和插入的优点

hashcode

hashCode通过hash函数计算得到，hashcode就是hash表中对应的位置。
每个对象都有hashcode，通过将对象的物理地址转换成一个整数，将整数通过hash计算得到hashcode

hashCode的存在只要是为了查找的快捷性。
HashCode 的存在只要是为了查找的快捷性，HashCode是用来在散列存储数据结构中确定对象的存储地址的，对于容器类设计 基本上都会涉及到hashcode，hashcode方法的主要作用是为了配合基于散列的集合一起正常运行。这样的散列集合包括HashSet,HashMap,以及HashTable
在对集合中进行插入操作时，集合内不允许有重复元素存在的，这样就引发了一个问题：

如何判别集合中是否存在了该对象了？

首先想到的方法是调用equals()方法，这个方法可行，但是如果集合中已经存在大量的数据，如果采用equals方法挨个比较 效率肯定是一个大问题。这个时候hashCode方法的作用就体现出来了，当集合要添加新的对象时，先调用该对象的hashCode方法，得到对应的hashcode值。

所以说hashCode方法的存在就是为了减少equals方法的调用次数