Java HashMap学习笔记（持续更新）

野性酷女 2022-07-14 08:07 264阅读 0赞

\#\#前言  
我最近在看Java 方面的知识，HashMap是绕不过去的一个知识点，为了加强记忆，我在这里做一个笔记，对HashMap进行一个大致的学习，希望能有所帮助。文中很多内容引用了别的前辈的文章里的内容，在这里谢谢他们~（如[Java HashMap工作原理及实现][Java HashMap]）

\#\#比较一些数据结构的特点  
\#\#\#数组  
数组存储区间是连续的，空间复杂度大。但数组的查找的时间复杂度小，为O(1)，但是插入和删除困难。

\#\#\#链表  
链表存储区间离散，空间复杂度很小，但查找时间复杂度很大，达O（N）。所以链表是查找困难，插入和删除容易。

\#\#\#HashMap  
HashMap是对Array与Link的折中处理，它的存储结构是由数组和链表共同完成的。HashMap既满足了数据的查找方便，同时不占用太多的内容空间。  
![hashmap图例][hashmap]

\#\#\#注：  
\#\#\#\#时间复杂度：  
算法中基本操作重复执行的次数是问题规模n的某个函数，用T(n)表示，若有某个辅助函数f(n)，使得当n趋近于无穷大时，T(n)/f(n)的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数。记作T(n)=O(f(n))，称O(f(n))为算法的渐进时间复杂度(O是数量级的符号 )，简称时间复杂度。

\#\#\#\#空间复杂度：  
空间复杂度就是指程序完全运行时，其代码段，静态和动态数据段占内外存储空间的大小。

\#\#什么时候用HashMap好，为什么会有HashMap这样的结构  
HashMap应该是取得快（get方法），存得时候动了一些脑筋（put方法）。而链表就是存的快，就是在末端链接一个节点，但是在取得时候就相对麻烦一些，需要全部遍历。数据结构（Collection的各个子类）在不同的场景下去使用，各有优势。

\#\#定义  
首先这是官方文档的定义:

Hash table based implementation of the Map interface. This implementation provides all of the optional map operations, and permits null values and the null key. (The HashMap class is roughly equivalent to Hashtable, except that it is unsynchronized and permits nulls.) This class makes no guarantees as to the order of the map; in particular, it does not guarantee that the order will remain constant over time.

中文翻译：

基于hash table的Map接口实现。这种实现提供了所有的map操作，并且允许空的key值和空的value值。（HashMap类大致相当于HashTable，但是它是不同步的并且允许null）这个类不保证印射的顺序；特别的是，它不保证顺序不随时间变化。

\#\#重要的参数

官方文档：

Initial capacity: The capacity is the number of buckets in the hash table, The initial capacity is simply the capacity at the time the hash table is created.
    Load factor: The load factor is a measure of how full the hash table is allowed to get before its capacity is automatically increased.

中文翻译：  
初始容积：容积是hashtable中的bucket的数量，初始的容积就是hashtable被创建时的容积。  
负载因子：负载因子是hashtable填充程度的大小，它衡量在容量自动扩充之前所能保持的最大的填充程度。

\#\#put函数（JDK 1.7）

put函数之我的见解：

*  当key是null的时候，特殊处理；
 *  对key的hashCode()做hash，然后再计算index;
 *  对当前数组索引为index上的链表进行循环查找；
 *  如果找到了当前链表上的一个节点，它的hash与待插入的hash相同，它的key.equals(待插入的key)为true，那么改变这个节点的值为带插入的value，同时返回当前节点旧的值。
 *  如果没有找到这样一个节点，逻辑继续向下执行，需要增加一个新的节点：如果增加一个新的节点之后的容积不够了，那么进行扩容，执行doubleCapacity()，计算出新的index索引值。
 *  新建一个节点，让它的next指向原来的表头（tab\[index\]），然后再把表头更新成新的节点的地址。

代码：

/**
         * Maps the specified key to the specified value.
         *
         * @param key
         *            the key.
         * @param value
         *            the value.
         * @return the value of any previous mapping with the specified key or
         *         {@code null} if there was no such mapping.
         */
        @Override public V put(K key, V value) {
            if (key == null) {
                return putValueForNullKey(value);
            }
    
            int hash = Collections.secondaryHash(key);//计算hash值
            HashMapEntry<K, V>[] tab = table;
            int index = hash & (tab.length - 1);//截断，使index不越界，位运算
            for (HashMapEntry<K, V> e = tab[index]; e != null; e = e.next) {
                if (e.hash == hash && key.equals(e.key)) {//这两个条件一定要同时满足（hashCode()和equals都可以重载）。
                    preModify(e);
                    V oldValue = e.value;
                    e.value = value;
                    return oldValue;//改变原来链表上元素的值
                }
            }
    
            // No entry for (non-null) key is present; create one
            modCount++;
            if (size++ > threshold) {//如果链表过长，扩容
                tab = doubleCapacity();
                index = hash & (tab.length - 1);
            }
            addNewEntry(key, value, hash, index);//新建一个hashentry，让它的next指向原来的表头（tab[index]），然后再把表头更新成新的hashentry的地址。
            return null;
        }

\#\#get函数

get函数之我的见解：

*  当key是null的时候，特殊处理；
 *  计算出当前key的hash值；
 *  计算出当前索引为hash & (tab.length - 1)，并对当前数组索引为index的链表进行遍历；
 *  如果当前节点的hash与查找key的hash相同并且它的key.equals(待查找的key)为true，或者当前节点的key值与待查找的key值都指向同一个内存地址（短路），那么返回当前节点的值vlaue；如果遍历之后没有找到这样的节点，那么就返回null。

代码：

/**
         * Returns the value of the mapping with the specified key.
         *
         * @param key
         *            the key.
         * @return the value of the mapping with the specified key, or {@code null}
         *         if no mapping for the specified key is found.
         */
        public V get(Object key) {
            if (key == null) {
                HashMapEntry<K, V> e = entryForNullKey;
                return e == null ? null : e.value;
            }
    
            int hash = Collections.secondaryHash(key);
            HashMapEntry<K, V>[] tab = table;
            for (HashMapEntry<K, V> e = tab[hash & (tab.length - 1)];
                    e != null; e = e.next) {
                K eKey = e.key;
                if (eKey == key || (e.hash == hash && key.equals(eKey))) {//这里也涉及到一个短路，加快效率
                    return e.value;
                }
            }
            return null;
        }

\#\#HashMap和Hashtable的比较  
\#\#\#相同点：  
HashMap几乎可以等价于Hashtable，它们都实现了Map接口。

\#\#\#不同点：

*  HashMap是非synchronized的；
 *  HashMap接受为null的键值(key)和值(value)；Hashtable不允许null作为key。
 *  相对而言HashMap性能会高一些（非synchronized）；

\#\#疑问  
当然HashMap里面也包含一些优化方面的实现，这里也说一下。比如：Entry\[\]的长度一定后，随着map里面数据的越来越长，这样同一个index的链就会很长，会不会影响性能？HashMap里面设置一个因素（也称为因子），随着map的size越来越大，Entry\[\]会以一定的规则加长长度。

\#\#hash解决冲突

*  二次探测再散列（通俗语言介绍）：如果在数组的某个索引的链表过长，而又有新的节点需要加入，那么就在当前数组索引附近查找可用存储单元，重复该动作直到找到可用存储单元为止。
 *  再哈希法
 *  链地址法
 *  建立一个公共溢出区（通俗语言介绍）：如果在数组的某个索引的链表容量已满，而又有新的节点需要加入，那么就把它放到公共溢出区中。

待续。。。

参考：  
[Java HashMap工作原理及实现][Java HashMap]

[HashMap实现原理分析][HashMap]

[算法的时间复杂度和空间复杂度][Link 1]

[HashMap和Hashtable的区别][HashMap_Hashtable]

[HashMap实现原理][HashMap 1]

[hash处理冲突][hash]

[浅谈Java中的hashcode方法][Java_hashcode]

[哈希表][Link 2]

[Java HashMap]: http://yikun.github.io/2015/04/01/Java-HashMap%E5%B7%A5%E4%BD%9C%E5%8E%9F%E7%90%86%E5%8F%8A%E5%AE%9E%E7%8E%B0/
[hashmap]: /images/20220714/870bc36fa5d84abda2ac078071fd4132.png
[HashMap]: http://blog.csdn.net/vking_wang/article/details/14166593
[Link 1]: http://blog.csdn.net/zolalad/article/details/11848739
[HashMap_Hashtable]: http://www.importnew.com/7010.html
[HashMap 1]: http://www.cnblogs.com/xwdreamer/archive/2012/05/14/2499339.html
[hash]: http://www.cnblogs.com/jillzhang/archive/2006/11/03/548671.html
[Java_hashcode]: http://www.cnblogs.com/dolphin0520/p/3681042.html
[Link 2]: http://www.cnblogs.com/jiewei915/archive/2010/08/09/1796042.html