wordpress 多站点配置文件,找人做网站需要什么条件,电商网站如何存储图片,js做网站好吗写在前面HashMap是Map族中最为常用的一种#xff0c;也是 Java Collection Framework 的重要成员。本文首先给出了 HashMap 的实质并概述了其与 Map、HashSet 的关系#xff0c;紧接着给出了 HashMap 在 JDK 中的定义#xff0c;并结合源码分析了其四种构造方式。最后#… 写在前面HashMap是Map族中最为常用的一种也是 Java Collection Framework 的重要成员。本文首先给出了 HashMap 的实质并概述了其与 Map、HashSet 的关系紧接着给出了 HashMap 在 JDK 中的定义并结合源码分析了其四种构造方式。最后通过对 HashMap 的数据结构、实现原理、源码实现三个方面的剖析深入到它底层 Hash 存储机制解释了其底层数组长度总是 2 的 n 次方的原因也揭示了其快速存取、扩容及扩容后的重哈希的原理与实现。本文所有关于HashMap的源码都是基于 JDK 1.6 的不同 JDK 版本之间也许会有些许差异但不影响我们对 HashMap 的数据结构、原理等整体的把握和了解。HashMap 概述Map 是 Key-Value 对映射的抽象接口该映射不包括重复的键即一个键对应一个值。HashMap 是 Java Collection Framework 的重要成员也是Map族(如下图所示)中我们最为常用的一种。简单地说HashMap 是基于哈希表的 Map 接口的实现以 Key-Value 的形式存在即存储的对象是 Entry (同时包含了 Key 和 Value) 。在HashMap中其会根据hash算法来计算key-value的存储位置并进行快速存取。特别地HashMap最多只允许一条Entry的键为Null(多条会覆盖)但允许多条Entry的值为Null。此外HashMap 是 Map 的一个非同步的实现。虽然 HashMap 和 HashSet 实现的接口规范不同但是它们底层的 Hash 存储机制完全相同。实际上HashSet 本身就是在 HashMap 的基础上实现的HashMap 在 JDK 中的定义HashMap实现了Map接口并继承 AbstractMap 抽象类其中 Map 接口定义了键值映射规则。和 AbstractCollection抽象类在 Collection 族的作用类似 AbstractMap 抽象类提供了 Map 接口的骨干实现以最大限度地减少实现Map接口所需的工作。HashMap 在JDK中的定义为public class HashMapK, V extends AbstractMapK, Vimplements MapK, V, Cloneable, Serializable {...}HashMap 的构造函数HashMap 一共提供了四个构造函数其中 默认无参的构造函数 和 参数为Map的构造函数 为 Java Collection Framework 规范的推荐实现其余两个构造函数则是 HashMap 专门提供的。1、HashMap()该构造函数意在构造一个具有 默认初始容量 (16) 和 默认负载因子(0.75) 的空 HashMap是 Java Collection Framework 规范推荐提供的其源码如下 /** * Constructs an empty HashMap with the default initial capacity * (16) and the default load factor (0.75). */public HashMap() {//负载因子:用于衡量的是一个散列表的空间的使用程度 this.loadFactor DEFAULT_LOAD_FACTOR; //HashMap进行扩容的阈值它的值等于 HashMap 的容量乘以负载因子 threshold (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);// HashMap的底层实现仍是数组只是数组的每一项都是一条链 table new Entry[DEFAULT_INITIAL_CAPACITY];init();}2、HashMap(int initialCapacity, float loadFactor)该构造函数意在构造一个 指定初始容量 和 指定负载因子的空 HashMap其源码如下 /** * Constructs an empty HashMap with the specified initial capacity and load factor. */public HashMap(int initialCapacity, float loadFactor) {//初始容量不能小于 0 if (initialCapacity 0)throw new IllegalArgumentException(Illegal initial capacity: initialCapacity);//初始容量不能超过 2^30 if (initialCapacity MAXIMUM_CAPACITY)initialCapacity MAXIMUM_CAPACITY;//负载因子不能小于 0 if (loadFactor 0 || Float.isNaN(loadFactor))throw new IllegalArgumentException(Illegal load factor: loadFactor);// HashMap 的容量必须是2的幂次方超过 initialCapacity 的最小 2^n int capacity 1;while (capacity initialCapacity)capacity 1; //负载因子 this.loadFactor loadFactor;//设置HashMap的容量极限当HashMap的容量达到该极限时就会进行自动扩容操作 threshold (int)(capacity * loadFactor);// HashMap的底层实现仍是数组只是数组的每一项都是一条链 table new Entry[capacity];init();}3、HashMap(int initialCapacity)该构造函数意在构造一个指定初始容量和默认负载因子 (0.75)的空 HashMap其源码如下 // Constructs an empty HashMap with the specified initial capacity and the default load factor (0.75) public HashMap(int initialCapacity) {this(initialCapacity, DEFAULT_LOAD_FACTOR); // 直接调用上述构造函数 }4、HashMap(Map? extends K, ? extends V m)该构造函数意在构造一个与指定 Map 具有相同映射的 HashMap其 初始容量不小于 16 (具体依赖于指定Map的大小)负载因子是 0.75是 Java Collection Framework 规范推荐提供的其源码如下 // Constructs a new HashMap with the same mappings as the specified Map. // The HashMap is created with default load factor (0.75) and an initial capacity // sufficient to hold the mappings in the specified Map. public HashMap(Map? extends K, ? extends V m) {// 初始容量不小于 16 this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) 1,DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR);putAllForCreate(m);}在这里我们提到了两个非常重要的参数初始容量 和 负载因子这两个参数是影响HashMap性能的重要参数。其中容量表示哈希表中桶的数量 (table 数组的大小)初始容量是创建哈希表时桶的数量负载因子是哈希表在其容量自动增加之前可以达到多满的一种尺度它衡量的是一个散列表的空间的使用程度负载因子越大表示散列表的装填程度越高反之愈小。HashMap 的数据结构哈希的相关概念Hash 就是把任意长度的输入(又叫做预映射 pre-image)通过哈希算法变换成固定长度的输出(通常是整型)该输出就是哈希值。这种转换是一种 压缩映射 也就是说散列值的空间通常远小于输入的空间。不同的输入可能会散列成相同的输出从而不可能从散列值来唯一的确定输入值。简单的说就是一种将任意长度的消息压缩到某一固定长度的息摘要函数。哈希的应用数据结构我们知道数组的特点是寻址容易插入和删除困难而链表的特点是寻址困难插入和删除容易。那么我们能不能综合两者的特性做出一种寻址容易插入和删除也容易的数据结构呢答案是肯定的这就是我们要提起的哈希表。事实上哈希表有多种不同的实现方法我们接下来解释的是最经典的一种方法 —— 拉链法我们可以将其理解为 链表的数组如下图所示我们可以从上图看到左边很明显是个数组数组的每个成员是一个链表。该数据结构所容纳的所有元素均包含一个指针用于元素间的链接。我们根据元素的自身特征把元素分配到不同的链表中去反过来我们也正是通过这些特征找到正确的链表再从链表中找出正确的元素。其中根据元素特征计算元素数组下标的方法就是 哈希算法。总的来说哈希表适合用作快速查找、删除的基本数据结构通常需要总数据量可以放入内存。在使用哈希表时有以下几个关键点hash 函数哈希算法的选择针对不同的对象(字符串、整数等)具体的哈希方法碰撞处理常用的有两种方式一种是open hashing即 拉链法另一种就是 closed hashing即开地址法(opened addressing)。HashMap 的数据结构我们知道在Java中最常用的两种结构是 数组 和 链表几乎所有的数据结构都可以利用这两种来组合实现HashMap 就是这种应用的一个典型。实际上HashMap 就是一个 链表数组如下是它数据结构从上图中我们可以形象地看出HashMap底层实现还是数组只是数组的每一项都是一条链。其中参数initialCapacity 就代表了该数组的长度也就是桶的个数。在第三节我们已经了解了HashMap 的默认构造函数的源码 /** * Constructs an empty HashMap with the default initial capacity * (16) and the default load factor (0.75). */public HashMap() {//负载因子:用于衡量的是一个散列表的空间的使用程度 this.loadFactor DEFAULT_LOAD_FACTOR; //HashMap进行扩容的阈值它的值等于 HashMap 的容量乘以负载因子 threshold (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);// HashMap的底层实现仍是数组只是数组的每一项都是一条链 table new Entry[DEFAULT_INITIAL_CAPACITY];init();}从上述源码中我们可以看出每次新建一个HashMap时都会初始化一个Entry类型的table数组其中 Entry类型的定义如下static class EntryK,V implements Map.EntryK,V {final K key; // 键值对的键 V value; // 键值对的值 EntryK,V next; // 下一个节点 final int hash; // hash(key.hashCode())方法的返回值 /** * Creates new entry. */Entry(int h, K k, V v, EntryK,V n) { // Entry 的构造函数 value v;next n;key k;hash h;}......}其中Entry为HashMap的内部类实现了 Map.Entry 接口其包含了键key、值value、下一个节点next以及hash值四个属性。事实上Entry 是构成哈希表的基石是哈希表所存储的元素的具体形式。HashMap 的快速存取下面我们结合JDK源码看HashMap 的存取实现。HashMap 的存储实现在 HashMap 中键值对的存储是通过 put(key,vlaue) 方法来实现的其源码如下 /** * Associates the specified value with the specified key in this map. * If the map previously contained a mapping for the key, the old * value is replaced. * * param key key with which the specified value is to be associated * param value value to be associated with the specified key * return the previous value associated with key, or null if there was no mapping for key. * Note that a null return can also indicate that the map previously associated null with key. */public V put(K key, V value) {//当key为null时调用putForNullKey方法并将该键值对保存到table的第一个位置 if (key null)return putForNullKey(value); //根据key的hashCode计算hash值 int hash hash(key.hashCode()); // ------- (1) //计算该键值对在数组中的存储位置哪个桶 int i indexFor(hash, table.length); // ------- (2) //在table的第i个桶上进行迭代寻找 key 保存的位置 for (EntryK,V e table[i]; e ! null; e e.next) { // ------- (3) Object k;//判断该条链上是否存在hash值相同且key值相等的映射若存在则直接覆盖 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; // 返回旧值 }}modCount; //修改次数增加1快速失败机制 //原HashMap中无该映射将该添加至该链的链头 addEntry(hash, key, value, i); return null;}对NULL键的特别处理putForNullKey()我们直接看其源码 /** * Offloaded version of put for null keys */private V putForNullKey(V value) {// 若keynull则将其放入table的第一个桶即 table[0] for (EntryK,V e table[0]; e ! null; e e.next) { if (e.key null) { // 若已经存在key为null的键则替换其值并返回旧值 V oldValue e.value;e.value value;e.recordAccess(this);return oldValue;}}modCount; // 快速失败 addEntry(0, null, value, 0); // 否则将其添加到 table[0] 的桶中 return null;}HashMap 中的哈希策略算法/*** Applies a supplemental hash function to a given hashCode, which* defends against poor quality hash functions. This is critical* because HashMap uses power-of-two length hash tables, that* otherwise encounter collisions for hashCodes that do not differ* in lower bits.** Note: Null keys always map to hash 0, thus index 0.*/
static int hash( int h )
{
/** This function ensures that hashCodes that differ only by* constant multiples at each bit position have a bounded* number of collisions (approximately 8 at default load factor).*/h ^ (h 20) ^ (h 12);return(h ^ (h 7) ^ (h 4) );
}正如JDK官方对该方法的描述那样使用hash()方法对一个对象的hashCode进行重新计算是为了防止质量低下的hashCode()函数实现。由于hashMap的支撑数组长度总是 2 的幂次通过右移可以使低位的数据尽量的不同从而使hash值的分布尽量均匀。通过上述hash()方法计算得到 Key 的 hash值 后怎么才能保证元素均匀分布到table的每个桶中呢我们会想到取模但是由于取模的效率较低HashMap 是通过调用上面的indexFor()方法处理的其不但简单而且效率很高对应源码如下所示/** * * Returns index for hash code h. * */static int indexFor( int h, int length ){return(h (length - 1) ); /* 作用等价于取模运算但这种方式效率更高 */}HashMap 中键值对的添加addEntry()我们直接看其源码 /** * Adds a new entry with the specified key, value and hash code to * the specified bucket. It is the responsibility of this * method to resize the table if appropriate. * * Subclass overrides this to alter the behavior of put method. * * 永远都是在链表的表头添加新元素 */void addEntry(int hash, K key, V value, int bucketIndex) {//获取bucketIndex处的链表 EntryK,V e table[bucketIndex];//将新创建的 Entry 链入 bucketIndex处的链表的表头 table[bucketIndex] new EntryK,V(hash, key, value, e);//若HashMap中元素的个数超过极限值 threshold则容量扩大两倍 if (size threshold)resize(2 * table.length);}HashMap 的扩容resize()随着HashMap中元素的数量越来越多发生碰撞的概率将越来越大所产生的子链长度就会越来越长这样势必会影响HashMap的存取速度。为了保证HashMap的效率系统必须要在某个临界点进行扩容处理该临界点就是HashMap中元素的数量在数值上等于thresholdtable数组长度*加载因子。但是不得不说扩容是一个非常耗时的过程因为它需要重新计算这些元素在新table数组中的位置并进行复制处理。所以如果我们能够提前预知HashMap 中元素的个数那么在构造HashMap时预设元素的个数能够有效的提高HashMap的性能。我们直接看其源码/** * * Rehashes the contents of this map into a new array with a * * larger capacity. This method is called automatically when the * * number of keys in this map reaches its threshold. * * * * If current capacity is MAXIMUM_CAPACITY, this method does not * * resize the map, but sets threshold to Integer.MAX_VALUE. * * This has the effect of preventing future calls. * * * * param newCapacity the new capacity, MUST be a power of two; * * must be greater than current capacity unless current * * capacity is MAXIMUM_CAPACITY (in which case value * * is irrelevant). * */void resize( int newCapacity ){Entry[] oldTable table;int oldCapacity oldTable.length;/* 若 oldCapacity 已达到最大值直接将 threshold 设为 Integer.MAX_VALUE */if ( oldCapacity MAXIMUM_CAPACITY ){threshold Integer.MAX_VALUE;return; /* 直接返回 */}/* 否则创建一个更大的数组 */Entry[] newTable new Entry[newCapacity];/* 将每条Entry重新哈希到新的数组中 */transfer( newTable );table newTable;threshold (int) (newCapacity * loadFactor); /* 重新设定 threshold */}HashMap 的重哈希transfer()重哈希的主要是一个重新计算原HashMap中的元素在新table数组中的位置并进行复制处理的过程我们直接看其源码/** * * Transfers all entries from current table to newTable. * */void transfer( Entry[] newTable ){/* 将原数组 table 赋给数组 src */Entry[] src table;int newCapacity newTable.length;/* 将数组 src 中的每条链重新添加到 newTable 中 */for ( int j 0; j src.length; j ){EntryK, V e src[j];if ( e ! null ){src[j] null; /* src 回收 *//* 将每条链的每个元素依次添加到 newTable 中相应的桶中 */do{EntryK, V next e.next;/* e.hash指的是 hash(key.hashCode())的返回值; *//* 计算在newTable中的位置注意原来在同一条子链上的元素可能被分配到不同的子链 */int i indexFor( e.hash, newCapacity );e.next newTable[i];newTable[i] e;e next;}while ( e ! null );}}}特别需要注意的是在重哈希的过程中原属于一个桶中的Entry对象可能被分到不同的桶因为HashMap 的容量发生了变化那么 h(length - 1) 的值也会发生相应的变化。极端地说如果重哈希后原属于一个桶中的Entry对象仍属于同一桶那么重哈希也就失去了意义。HashMap 的读取实现相对于HashMap的存储而言读取就显得比较简单了。因为HashMap只需通过key的hash值定位到table数组的某个特定的桶然后查找并返回该key对应的value即可源码如下/** * * Returns the value to which the specified key is mapped, * * or {code null} if this map contains no mapping for the key. * * pMore formally, if this map contains a mapping from a key * * {code k} to a value {code v} such that {code (keynull ? knull : * * key.equals(k))}, then this method returns {code v}; otherwise * * it returns {code null}. (There can be at most one such mapping.) * pA return value of {code null} does not inecessarily/i * * indicate that the map contains no mapping for the key; its also * * possible that the map explicitly maps the key to {code null}. * * The {link #containsKey containsKey} operation may be used to * * distinguish these two cases. * see #put(Object, Object) * */public V get( Object key ){/* 若为null调用getForNullKey方法返回相对应的value */if ( key null )/* 从table的第一个桶中寻找 key 为 null 的映射若不存在直接返回null */return(getForNullKey() );/* 根据该 key 的 hashCode 值计算它的 hash 码 */int hash hash( key.hashCode() );/* 找出 table 数组中对应的桶 */for ( EntryK, V e table[indexFor( hash, table.length )];e ! null;e e.next ){Object k;/* 若搜索的key与查找的key相同则返回相对应的value */if ( e.hash hash ( (k e.key) key || key.equals( k ) ) )return(e.value);}return(null);}针对键为NULL的键值对HashMap 提供了专门的处理getForNullKey()其源码如下/** * * Offloaded version of get() to look up null keys. Null keys map * * to index 0. This null case is split out into separate methods * * for the sake of performance in the two most commonly used * * operations (get and put), but incorporated with conditionals in * * others. * */private V getForNullKey(){/* 键为NULL的键值对若存在则必定在第一个桶中 */for ( EntryK, V e table[0]; e ! null; e e.next ){if ( e.key null )return(e.value);}/* 键为NULL的键值对若不存在则直接返回 null */return(null);}因此调用HashMap的get(Object key)方法后若返回值是 NULL则存在如下两种可能该 key 对应的值就是 null;HashMap 中不存在该 key。 转载于:https://blog.51cto.com/14207296/2380981
