[数据结构与算法]java-HashMap的源码分析

/*
map的实现类结构；

Map；双列数据，存储key-value对的数据，类似高中的函数
—HashMap；作为Map的主要实现类，线程不安全的，效率高，存储null的key和value
—LinkedHashMap；继承了HashMap在原有的基础上增加了两个属性（指针），
保证遍历map元素时可以按照添加的顺序实现遍历
对于频繁的遍历操作此类的效率更高
—TreeMap；保证按照添加的key-value对进行排序，实现了排序遍历
—Hashtable；作为古老的实现类，线程安全，效率低，不能存储null的key和value
------properties；用来处理和配置文件，key和value都是String类型的
HashMap的原理分析；
HashMap是存在key-value的存储的。JDK8中一个键值对；key-value构成了一个Node对象
Map中的key；无序的，不可重复的，所以是使用Set存储的；以HashMap为例key所在的类要重写equals（）和hashcode（）
Map中的value；无序的，可重复的，使用Collection储存；value所在的类要重写equals（）

HashMap在JDK7与JDK8中的实现原理

JDK7；
—在new HashMap();之后底层会创建一个长度是16的一维数组Entry[] table;
当执行添加操作put时（可能已经执行过多次）
首先调用Key所在类的hashCode()计算key的hash值，此hash值通过某种算法之后得到在数组Entry中的位置。
----如果该位置为空，则直接将此数据存到数组中
----如果该位置不为空；（此时说明该位置已经存在一个或多个数据）
--------比较key的哈希值与该位置一个或多个数据的哈希值
--------------如果哈希值都不同，则添加成功；
---------------如果key的hash值与该位置一个数据hash值相同，则调用equls()
---------------------------如果equals返回Ture；则将key的value覆盖对应返回Ture的键值对的value
---------------------------如果equals返回false；则此时key添加成功
注；当算出哈希值并且确认存储位置之后所在位置存在数据的情况下，采用的时链表方式存储

扩容问题；
当涉及到扩容时，默认扩容会扩容为原来的二倍，并且将原来的数据复制到新的数组中。

JDK8中；

1，JDK8中一开始没有创建固定容量大小的数组，只有当首次调用put时才会创建一个大小为16的数组
2，JDK8中的数组用的时Node数组，但是Node时继承了Entry的
3，jdk7底层只有数组+链表，而jdk8中有数据+链表+红黑树
注；当数组中的某一个索引上的链表长度大于8并且数组长度大于64时，此时该索引位置上所有数据的存储方式改为红黑树存储

*/

*/在看源码分析之前的几个重要的数据

DEFAJLT_INITIAL_CAPACITY;HashMap的默认容量，16
MAXIMUM-CAPACITY;HashMap的最大支持容量；
DEFAULT_LOAD_FACTOR;HashMap的默认加载因子；0.75
TREEIFY_THRESHOLD;Bucket;Bucket中链表长度大于该默认值，转换为红黑树
UNTREEIFY_THRESHOLD;Bucket中红黑树存储的Node小于该默认值转换为链表
MIN_TREEIFY_CAPACITY；桶中的Node被树化时最小的hash表容量
loadFactor；填充因子
threshold；扩容的临界值=容量*填充因子
*/

//JDK8中的源码分析
//当new HashMap( )；时底层的数组当new HashMap的时候并没有直接创建数组，
空参构造器为；

 public HashMap() {
   this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
    }

当put新的数据时调用putVa

public V put(K key, V value) {
   return putVal(hash(key), key, value, false, true);
   }

putVal()源码；
/*

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node<K,V>[] tab; Node<K,V> p; int n, i;

        //这里如果第一次添加数据会调用resize()方法（底层创建了长度为16的Node数组）
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;

        //哈希值通过算法得到数据存储在数组中的索引，如果当前索引位置没有元素，则创建一个新的Node来存放需要添加的数据
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);

        //如果索引位置有值，则进入else
        else {
            Node<K,V> e; K k;


            //如果传入的数据的哈希值和所在索引处的数据哈希值相等并且equals确定了两者相等则执行e = p再在最后进行value值的替换；
            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);

                //传入数据与索引位置数据hash值不等或者equals不等则进入else
            else {
                for (int binCount = 0; ; ++binCount) {
                //如果p的下一个元素为空，则p的下一个数据指向需要添加的数据，数据添加成功
                    if ((e = p.next) == null) {
                        p.next = newNode(hash, key, value, null);

                        //当链表的长度超过8并且数组长度大于64则变成红黑树如果数组长度没有超过64则扩容
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash);
                        break;
                    }

                    如果传入的数据的哈希值和所在索引处的数据哈希值相等并且equals确定了两者相等，则在最
                    //                }
                    //            }
                    //
                    //            //进行将相同key的value值替换
                    //            if (e != null) { // existing mapping for key后进行value值的替换
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        ++modCount;
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;
    }

*/

注；HashMap和ArrayList不一样，当它的数据大于12之后就会扩容了，究其原因；提前扩容是为了防止链表形式少，数组利用率更高，
所以加载因子为0.75

/*
LinkedHashMap的底层源码与实现；

LinkedHashMap继承了HashMap(对于频繁的遍历可以选择用LinkedHashMap替换HashMap)
当new LinkedHashMap之后底层源码为；

 public LinkedHashMap() {
        super();
        accessOrder = false;
    }

空参构造器用了super();所以也就继承了map中的方法
在LinkedHashMap中重写HashMap的方法是newNode()方法，并且在底层创建的是一个Entry对象源码为；

static class Entry<K,V> extends HashMap.Node<K,V> {
        Entry<K,V> before, after;
        Entry(int hash, K key, V value, Node<K,V> next) {
            super(hash, key, value, next);
        }
    }

最大的改动就是在Entry中加入了before和after两个属性来判断加入元素的先后顺序，所以可以按添加的顺序输出

例子；

public class HashMapTest {
    public static void main(String[] args) {
        LinkedHashMap<Object, Object> linkedHashMap = new LinkedHashMap<>();
        linkedHashMap.put("dd",123);
        linkedHashMap.put("AA",456);
        linkedHashMap.put("cc",789);
        linkedHashMap.put("ee",666);
        System.out.println(linkedHashMap);//{dd=123, AA=456, cc=789, ee=666}
    }
}