数据结构中有数组和链表来实现对数据的存储，但这两者基本上是两个极端。

数组：存储区间是连续的，占用内存严重，故空间复杂的很大。但数组的二分查找时间复杂度小，为O(1)；数组的特点是：寻址容易，插入和删除困难；

Java中主要是ArrayList和Vector，动态数组

链表：存储区间离散，占用内存比较宽松，故空间复杂度很小，但时间复杂度很大，达O（N）。链表的特点是：寻址困难，插入和删除容易。

java中的LinkedList实现了双向链表

哈希表：一种寻址容易、插入也容易的数据结构

哈希表有多种不同的实现方法，我接下来解释的是最常用的一种方法—— 拉链法，我们可以理解为“链表的数组” ，如图：

从上图我们可以发现哈希表是由数组+链表组成的

HashMap其实也是一个线性的数组实现的,所以可以理解为其存储数据的容器就是一个线性数组。这可能让我们很不解，一个线性的数组怎么实现按键值对来存取数据呢？这里HashMap有做一些处理。

　　首先HashMap里面实现一个静态内部类Entry，其重要的属性有 key , value, next，从属性key,value我们就能很明显的看出来Entry就是HashMap键值对实现的一个基础bean，我们上面说到HashMap的基础就是一个线性数组，这个数组就是Entry[]，Map里面的内容都保存在Entry[]里面。

HashMap的存取实现

既然是线性数组，为什么能随机存取？这里HashMap用了一个小算法，大致是这样实现：

// 存储时: 
int hash = key.hashCode(); // 这个hashCode方法这里不详述,只要理解每个key的hash是一个固定的int值 
int index = hash % Entry[].length; 
Entry[index] = value; 
 
// 取值时: 
int hash = key.hashCode(); 
int index = hash % Entry[].length; 
return Entry[index];

1）put

疑问：如果两个key通过hash%Entry[].length得到的index相同，会不会有覆盖的危险？

这里HashMap里面用到链式数据结构的一个概念。上面我们提到过Entry类里面有一个next属性，作用是指向下一个Entry。打个比方，第一个键值对A进来，通过计算其key的hash得到的index=0，记做:Entry[0] = A。一会后又进来一个键值对B，通过计算其index也等于0，现在怎么办？HashMap会这样做:B.next = A,Entry[0] = B,如果又进来C,index也等于0,那么C.next = B,Entry[0] = C；这样我们发现index=0的地方其实存取了A,B,C三个键值对,他们通过next这个属性链接在一起。所以疑问不用担心。也就是说数组中存储的是最后插入的元素。到这里为止，HashMap的大致实现，我们应该已经清楚了。

<span style="font-family:SimSun;font-size:14px;"> public V put(K key, V value) { 
        if (key == null) 
            return putForNullKey(value); //null总是放在数组的第一个链表中 
        int hash = hash(key.hashCode()); 
        int i = indexFor(hash, table.length); 
        //遍历链表 
        for (Entry<K,V> e = table[i]; e != null; e = e.next) { 
            Object k; 
            //如果key在链表中已存在，则替换为新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++; 
        addEntry(hash, key, value, i); 
        return null; 
    } 
void addEntry(int hash, K key, V value, int bucketIndex) { 
    Entry<K,V> e = table[bucketIndex]; 
    table[bucketIndex] = new Entry<K,V>(hash, key, value, e); //参数e, 是Entry.next 
    //如果size超过threshold，则扩充table大小。再散列 
    if (size++ >= threshold) 
            resize(2 * table.length); 
}

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

2）get

<span style="font-family:SimSun;font-size:14px;">public V get(Object key) { 
        if (key == null) 
            return getForNullKey(); 
        int hash = hash(key.hashCode()); 
        //先定位到数组元素，再遍历该元素处的链表 
        for (Entry<K,V> e = table[indexFor(hash, table.length)]; 
             e != null; 
             e = e.next) { 
            Object k; 
            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) 
                return e.value; 
        } 
        return null; 
}<span style="background-color: rgb(255, 255, 255);">

3）null key的存取

null key总是存放在Entry[]数组的第一个元素。

 private V putForNullKey(V value) { 
        for (Entry<K,V> e = table[0]; e != null; e = e.next) { 
            if (e.key == null) { 
                V oldValue = e.value; 
                e.value = value; 
                e.recordAccess(this); 
                return oldValue; 
            } 
        } 
        modCount++; 
        addEntry(0, null, value, 0); 
        return null; 
    } 
  
    private V getForNullKey() { 
        for (Entry<K,V> e = table[0]; e != null; e = e.next) { 
            if (e.key == null) 
                return e.value; 
        } 
        return null; 
    }

4）确定数组index：hashcode % table.length取模

HashMap存取时，都需要计算当前key应该对应Entry[]数组哪个元素，即计算数组下标；

indexFor中的h & (length-1)就相当于h%length，用于计算index也就是在table数组中的下标
hash方法是对hashcode进行二次散列，以获得更好的散列值
为了更好理解这里我们可以把这两个方法简化为 int index= key.hashCode()/table.length,以put中的方法为例可以这样替换

算法如下：

int hash = hash(key.hashCode());//计算hash

int i = indexFor(hash,table.length);//计算在数组中的存储位置

//上面两行可以这样简化：

int i = key.hashCode()%table.length;

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); 
    } 
    static int indexFor(int h, int length) { 
        return h & (length-1); 
    }

按位取并，作用上相当于取模mod或者取余%。

这意味着数组下标相同，并不表示hashCode相同。

5）table初始大小

HashMap默认初始化时会创建一个默认容量为16的Entry数组，默认加载因子为0.75，同时设置临界值为16*0.75

 public HashMap(int initialCapacity, float loadFactor) { 
        ..... 
        // Find a power of 2 >= initialCapacity 
        int capacity = 1; 
        while (capacity < initialCapacity) 
            capacity <<= 1; 
        this.loadFactor = loadFactor; 
        threshold = (int)(capacity * loadFactor); 
        table = new Entry[capacity]; 
        init(); 
    }

注意table初始大小并不是构造函数中的initialCapacity！！

而是 >= initialCapacity的2的n次幂！！！！

6）clear（）方法

clear方法非常简单，就是遍历table然后把每个位置置为null，同时修改元素个数为0

需要注意的是clear方法只会清楚里面的元素，并不会重置capactiy

 public void clear() { 
        modCount++; 
        Entry[] tab = table; 
        for (int i = 0; i < tab.length; i++) 
            tab[i] = null; 
        size = 0; 
    }

7）containsKey和containsValue

containsKey方法是先计算hash然后使用hash和table.length取摸得到index值，遍历table[index]元素查找是否包含key相同的值

<span style="font-family:SimSun;font-size:14px;">public boolean containsKey(Object key) { 
        return getEntry(key) != null; 
    } 
final Entry<K,V> getEntry(Object key) { 
        int hash = (key == null) ? 0 : hash(key.hashCode()); 
        for (Entry<K,V> e = table[indexFor(hash, table.length)]; 
             e != null; 
             e = e.next) { 
            Object k; 
            if (e.hash == hash && 
                ((k = e.key) == key || (key != null && key.equals(k)))) 
                return e; 
        } 
        return null; 
    }

containsValue方法就比较粗暴了，就是直接遍历所有元素直到找到value，由此可见HashMap的containsValue方法本质上和普通数组和list的contains方法没什么区别，你别指望它会像containsKey那么高效

public boolean containsValue(Object value) { 
    if (value == null) 
            return containsNullValue(); 
 
    Entry[] tab = table; 
        for (int i = 0; i < tab.length ; i++) 
            for (Entry e = tab[i] ; e != null ; e = e.next) 
                if (value.equals(e.value)) 
                    return true; 
    return false; 
    }

8）remove方法

remove方法和put get类似，计算hash，计算index，然后遍历查找，将找到的元素从table[index]链表移除

public V remove(Object key) { 
        Entry<K,V> e = removeEntryForKey(key); 
        return (e == null ? null : e.value); 
    } 
    final Entry<K,V> removeEntryForKey(Object key) { 
        int hash = (key == null) ? 0 : hash(key.hashCode()); 
        int i = indexFor(hash, table.length); 
        Entry<K,V> prev = table[i]; 
        Entry<K,V> e = prev; 
 
        while (e != null) { 
            Entry<K,V> next = e.next; 
            Object k; 
            if (e.hash == hash && 
                ((k = e.key) == key || (key != null && key.equals(k)))) { 
                modCount++; 
                size--; 
                if (prev == e) 
                    table[i] = next; 
                else 
                    prev.next = next; 
                e.recordRemoval(this); 
                return e; 
            } 
            prev = e; 
            e = next; 
        } 
 
        return e; 
    }

解决hash冲突的办法

开放定址法（线性探测再散列，二次探测再散列，伪随机探测再散列）
再哈希法
链地址法
建立一个公共溢出区

Java中hashmap的解决办法就是采用的链地址法。

再散列rehash过程

当哈希表的容量超过默认容量时，必须调整table的大小。当容量已经达到最大可能值时，那么该方法就将容量调整到Integer.MAX_VALUE返回，这时，需要创建一张新表，将原表的映射到新表中。

具体过程为：先创建一个容量为table.length*2的新table，修改临界值，然后把table里面元素计算hash值并使用hash与table.length*2重新计算index放入到新的table里面
这里需要注意下是用每个元素的hash全部重新计算index，而不是简单的把原table对应index位置元素简单的移动到新table对应位置

 /** 
     * 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; 
        if (oldCapacity == MAXIMUM_CAPACITY) { 
            threshold = Integer.MAX_VALUE; 
            return; 
        } 
        Entry[] newTable = new Entry[newCapacity]; 
        transfer(newTable); 
        table = newTable; 
        threshold = (int)(newCapacity * loadFactor); 
    } 
  
    /** 
     * Transfers all entries from current table to newTable. 
     */ 
    void transfer(Entry[] newTable) { 
        Entry[] src = table; 
        int newCapacity = newTable.length; 
        for (int j = 0; j < src.length; j++) { 
            Entry<K,V> e = src[j]; 
            if (e != null) { 
                src[j] = null; 
                do { 
                    Entry<K,V> next = e.next; 
                    //重新计算index 
                    int i = indexFor(e.hash, newCapacity); 
                    e.next = newTable[i]; 
                    newTable[i] = e; 
                    e = next; 
                } while (e != null); 
            } 
        } 
    }

转载出处：
http://www.cnblogs.com/lzrabbit/p/3721067.html

转载出处：
http://blog.csdn.net/vking_wang/article/details/14166593

HashMap的性能参数：

HashMap 包含如下几个构造器：

HashMap()：构建一个初始容量为 16，负载因子为 0.75 的 HashMap。

HashMap(int initialCapacity)：构建一个初始容量为 initialCapacity，负载因子为 0.75 的 HashMap。

HashMap(int initialCapacity, float loadFactor)：以指定初始容量、指定的负载因子创建一个 HashMap。

HashMap的基础构造器HashMap(int initialCapacity, float loadFactor)带有两个参数，它们是初始容量initialCapacity和加载因子loadFactor。

initialCapacity：HashMap的最大容量，即为底层数组的长度。

loadFactor：负载因子loadFactor定义为：散列表的实际元素数目(n)/ 散列表的容量(m)。

负载因子衡量的是一个散列表的空间的使用程度，负载因子越大表示散列表的装填程度越高，反之愈小。对于使用链表法的散列表来说，查找一个元素的平均时间是O(1+a)，因此如果负载因子越大，对空间的利用更充分，然而后果是查找效率的降低；如果负载因子太小，那么散列表的数据将过于稀疏，对空间造成严重浪费。

HashMap的实现中，通过threshold字段来判断HashMap的最大容量：

   Java代码  

 threshold = (int)(capacity * loadFactor);

结合负载因子的定义公式可知，threshold就是在此loadFactor和capacity对应下允许的最大元素数目，超过这个数目就重新resize，以降低实际的负载因子。默认的的负载因子0.75是对空间和时间效率的一个平衡选择。当容量超出此最大容量时， resize后的HashMap容量是容量的两倍：

   Java代码  

 if (size++ >= threshold)     
     resize(2 * table.length);

Fail-Fast机制：

我们知道java.util.HashMap不是线程安全的，因此如果在使用迭代器的过程中有其他线程修改了map，那么将抛出ConcurrentModificationException，这就是所谓fail-fast策略。

这一策略在源码中的实现是通过modCount域，modCount顾名思义就是修改次数，对HashMap内容的修改都将增加这个值，那么在迭代器初始化过程中会将这个值赋给迭代器的expectedModCount。

   Java代码  
     
 HashIterator() {  
     expectedModCount = modCount;  
     if (size > 0) { // advance to first entry  
     Entry[] t = table;  
     while (index < t.length && (next = t[index++]) == null)  
         ;  
     }  
 }  

在迭代过程中，判断modCount跟expectedModCount是否相等，如果不相等就表示已经有其他线程修改了Map：

注意到modCount声明为volatile，保证线程之间修改的可见性。

   Java代码  
     
 final Entry<K,V> nextEntry() {     
     if (modCount != expectedModCount)     
         throw new ConcurrentModificationException();  

在HashMap的API中指出：

由所有HashMap类的“collection 视图方法”所返回的迭代器都是快速失败的：在迭代器创建之后，如果从结构上对映射进行修改，除非通过迭代器本身的 remove 方法，其他任何时间任何方式的修改，迭代器都将抛出ConcurrentModificationException。因此，面对并发的修改，迭代器很快就会完全失败，而不冒在将来不确定的时间发生任意不确定行为的风险。

注意，迭代器的快速失败行为不能得到保证，一般来说，存在非同步的并发修改时，不可能作出任何坚决的保证。快速失败迭代器尽最大努力抛出 ConcurrentModificationException。因此，编写依赖于此异常的程序的做法是错误的，正确做法是：迭代器的快速失败行为应该仅用于检测程序错误。

原创文章，作者：ItWorker，如若转载，请注明出处：https://blog.ytso.com/industrynews/13770.html

Java中HashMap的实现机制详解编程语言

1）put

疑问：如果两个key通过hash%Entry[].length得到的index相同，会不会有覆盖的危险？

2）get

3）null key的存取

4）确定数组index：hashcode % table.length取模

5）table初始大小

6）clear（）方法

7）containsKey和containsValue

8）remove方法

解决hash冲突的办法

再散列rehash过程

发表回复

Java中HashMap的实现机制详解编程语言

1）put

疑问：如果两个key通过hash%Entry[].length得到的index相同，会不会有覆盖的危险？

2）get

3）null key的存取

4）确定数组index：hashcode % table.length取模

5）table初始大小

6）clear（）方法

7）containsKey和containsValue

8）remove方法

解决hash冲突的办法

再散列rehash过程

相关推荐

发表回复