JAVA-HashMap实现原理

一、hashmap实现原理

1. hashmap概述

　　hashmap是基于哈希表的map接口的非同步实现。它允许存入null值和null键。它不保证存入元素的顺序与操作顺序一致，主要是不保证元素的顺序永恒不变。

　　hashmap底层的数据结构是一个“链表散列“的数据结构，即数组和链表的结合体。

　　从上图中可以看出，hashmap底层就是一个数组，数组的每一个位置上又是一个链表。

2.底层代码分析

　　hashmap<string,object> map = new hashmap<string,object>();//当我们创建一个hashmap的时候，会产生哪些操作？

　　

public class hashmap<k,v>
    extends abstractmap<k,v>
    implements map<k,v>, cloneable, serializable
{

    /**
     * 初始化容量-16
     */
    static final int default_initial_capacity = 1 << 4; 

    
    static final int maximum_capacity = 1 << 30;

   
    static final float default_load_factor = 0.75f;

    /**
     * 一个空的entry数组
     */
    static final entry<?,?>[] empty_table = {};

    /**
     * 存储元素的数组，自动扩容
     */
    transient entry<k,v>[] table = (entry<k,v>[]) empty_table;
　　

 　　/**
    * 键值对
    */
　　static class entry<k,v> implements map.entry<k,v> {
        final k key;
        v value;
        entry<k,v> next;
        int hash;

        /**
         * 初始化方法
         */
        entry(int h, k k, v v, entry<k,v> n) {
            value = v;
            next = n;
            key = k;
            hash = h;
        }
    
　　/** * 1.初始化方法 */
　　public hashmap() {
        this(default_initial_capacity, default_load_factor);
    }

　　/** * 2.初始化方法 */
　　public hashmap(int initialcapacity, float loadfactor) {
        if (initialcapacity < 0)
            throw new illegalargumentexception("illegal initial capacity: " +
                                               initialcapacity);
        if (initialcapacity > maximum_capacity)
            initialcapacity = maximum_capacity;
        if (loadfactor <= 0 || float.isnan(loadfactor))
            throw new illegalargumentexception("illegal load factor: " +
                                               loadfactor);

        this.loadfactor = loadfactor;
        threshold = initialcapacity;
        init();
    }

}

public class linkedhashmap<k,v>
    extends hashmap<k,v>
    implements map<k,v>
{

    private static final long serialversionuid = 3801124242820219131l;

    /**
     * 双重链表的一个第一个元素
     */
    private transient entry<k,v> header;
　　/** * 3.初始化方法 */
    @override
    void init() {
        header = new entry<>(-1, null, null, null);
        header.before = header.after = header;
    }

 　　/**
     * linkedhashmap 中的entry继承了hashmap中的entry
     */
    private static class entry<k,v> extends hashmap.entry<k,v> {
        // these fields comprise the doubly linked list used for iteration.
        entry<k,v> before, after;
　　　　　/** * 4.初始化方法 */
        entry(int hash, k key, v value, hashmap.entry<k,v> next) {
            super(hash, key, value, next);
        }

}

通过 hashmap中的成员变量entry<k,v>[] table，可以看出，entry就是数组中的元素，每个entry就是一个key-value键值对，它持有一个只指向下一个元素的引用，这就构成了链表的数据结构。

关于数组的初始化时机不是我们在new hashtable的时候，实在我们第一次执行put()操作的时候：

　　public v put(k key, v value) {
        if (table == empty_table) {
　　　　　　　/**如果这是一个空的table，就进行初始化*/
            inflatetable(threshold);
        }
        if (key == null)
            return putfornullkey(value);
　　　　　/**通过hash算法获取hash值*/
        int hash = hash(key);
　　　　　　/**根据hash值获取在数组中的位置*/
        int i = indexfor(hash, table.length);
　　　　/**获取数组在 i 位置上的链表，并进行循环*/
        for (entry<k,v> e = table[i]; e != null; e = e.next) {
            object k;
　　　　　　　/**如果hash值相等，并且value值相等，value值会进行覆盖，返回之前的value*/
            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                v oldvalue = e.value;
                e.value = value;
                e.recordaccess(this);
                return oldvalue;
            }
        }
　　　　// 如果在i位置的entry为null，或者value的值不相同，执行addectity()方法
        modcount++;
        addentry(hash, key, value, i);
        return null;
    }

　　void addentry(int hash, k key, v value, int bucketindex) {
　　　　// 如果当前数组已经饱和，并且当前位置的entry不是null，数组进行扩容
    　　if ((size >= threshold) && (null != table[bucketindex])) {
        　　// 扩容操作，原数组需要重新计算在新数组中的位置，并放进去，这里会产生性能损耗
　　　　　　　// 如果我们能已知元素个数，就可以在创建的时候进行生命即可。
　　　　　　　resize(2 * table.length);
        　　hash = (null != key) ? hash(key) : 0;
        　　bucketindex = indexfor(hash, table.length);
    　　}
　　　　// 创建新的entry
    　　createentry(hash, key, value, bucketindex);
　　}
　　
　　void resize(int newcapacity) {
    　　entry[] oldtable = table;
    　　int oldcapacity = oldtable.length;
    　　if (oldcapacity == maximum_capacity) {
        　　threshold = integer.max_value;
        　　return;
    　　}

    　　entry[] newtable = new entry[newcapacity];
    　　transfer(newtable, inithashseedasneeded(newcapacity));
    　　table = newtable;
    　　threshold = (int)math.min(newcapacity * loadfactor, maximum_capacity + 1);
　　}
　　void createentry(int hash, k key, v value, int bucketindex) {
    　　entry<k,v> e = table[bucketindex];
    　　table[bucketindex] = new entry<>(hash, key, value, e);
    　　size++;
　　}

　　entry(int h, k k, v v, entry<k,v> n) {
    　　value = v;
    　　next = n;
    　　key = k;
    　　hash = h;
　　}

根据hash算法得出元素在数组中的存放位置，如果改位置上已经存在元素，那么这个位置上的元素将以链表的形式存放，新加入的放在头部，后加入的在尾部。

 1 final int hash(object k) {
 2     　　int h = hashseed;
 3     　　if (0 != h && k instanceof string) {
 4         　　return sun.misc.hashing.stringhash32((string) k);
 5     　　}
 6 
 7     　　h ^= k.hashcode();
 8     　　h ^= (h >>> 20) ^ (h >>> 12);
 9     　　return h ^ (h >>> 7) ^ (h >>> 4);
10 　　}

根据key的hash值来决定元素在数组中的位置，如何计算这个位置就是hash算法。通过hash算法尽量使得数组的每个位置上都只有一个元素，当我们再次get()的时候，直接去数组中取就可以，不用再遍历链表。

hash(int h)根据key的hashcode重新计算一次散列，此算法加入了高位计算，防止低位不变，高位变化时，造成hash的冲突。