文档章节

HashMap原理和代码浅析

球球
 球球
发布于 2017/01/31 20:49
字数 4159
阅读 8
收藏 0

hashCode介绍

分析HashMap之前先介绍下什么Hashcode(散列码)。它是一个int,每个对象都会有一个hashcode,它在内存的存放位置是放在对象的头部(对象头部存放的信息有hashcode,指向Class的引用,和一些有关垃圾回收信息)。需要注意的是,如果在你的类中覆盖了Object的equals(Object)方法,那么你必须覆盖hashCode方法,不然,当你使用HashMap,HashSet,HashTable时会出现问题。这个问题在《effective Java中文版》这本书里面有详细的介绍。下面只是简要摘除来3个主要的原因 (摘自Object规范): 
(1)在程序的执行期间,只要对象的equals方法的比较操作所用到的信息没有被修改,那么对这同一对象调用多次,hashCode方法必须始终如一的返回同一个值,在同一个应用的多次执行过程中,每次执行所返回的值可以不同。 
(2)如果两个对象,根据equas方法比较是想法的,那么掉哦你给这两个对象中任意一个对象的hashCode方法都必须产生相同的整数结果。 
(3)如果两个对象根据equals方法比较是不相等的,那么调用这两个对象中任意一个对象的hashCode方法,则不一定要产生不同的整数结果,但是程序员应该知道,给不同的对象产生截然不同的整数结果,有可能提高散列表的性能。 
下面以String的hashCode举个列子: 
String类重写了Object类中的equals和hashCode方法,原因很简单,Object中的equals方法是指比较两个对象是不是指向同一个引用对象,而String类指需要比较内容相不相等就可以了。所以String覆盖了equals方法,同时覆盖了hashCode方法(具体为什么同时覆盖两者参考以上3点以及http://blog.csdn.net/michaellufhl/article/details/5833188)。 
String中的hashcode算法很简单如下:

@Override public int hashCode() {
        int hash = hashCode;
        if (hash == 0) {
            if (count == 0) {
                return 0;
            }
            for (int i = 0; i < count; ++i) {
                hash = 31 * hash + charAt(i);
            }
            hashCode = hash;
        }
        return hash;
    }

 

比如一个字符串“abc”(a的ascii码是97),它的hashcode算法是: 
h = 31 * 0 + 97 ==> h = 97; 
h = 31 * 97 + 98 ==> h = 3105; 
h = 31 * 3105 + 99 ==> h = 96354; 
所以“abc”的hashCode就是96354 。

以上内容参考文档:

http://www.iteye.com/topic/838030

HashMap的存储结构

HashMap是以链法表的形式存储的,与其对应的是开放地址发。两种方法的比较:链表法和开放地址法。链表法就是将相同hash值的对象组织成一个链表放在hash值对应的槽位;开放地址法是通过一个探测算法,当某个槽位已经被占据的情况下继续查找下一个可以使用的槽位。java.util.HashMap采用的链表法的方式,链表是单向链表,因此在删除过程中要自己维持prev节点。 
HashMap的存储结构图(来自网络): 
这里写图片描述 
HashMap的功能是通过“键(key)”能够快速的找到“值”。下面我们分析下HashMap存数据的基本流程: 
1、 当调用put(key,value)时,首先获取key的hashcode。 
2、 再把hash通过一下运算得到一个int h. 
hash ^= (hash >>> 20) ^ (hash >>> 12); 
int h = hash ^ (hash >>> 7) ^ (hash >>> 4); 
为什么要经过这样的运算呢?这就是HashMap的高明之处。先看个例子,一个十进制数32768(二进制1000 0000 0000 0000),经过上述公式运算之后的结果是35080(二进制1000 1001 0000 1000)。看出来了吗?或许这样还看不出什么,再举个数字61440(二进制1111 0000 0000 0000),运算结果是65263(二进制1111 1110 1110 1111),现在应该很明显了,它的目的是让“1”变的均匀一点,散列的本意就是要尽量均匀分布。那这样有什么意义呢?看第3步。 
3、 得到h之后,把h与HashMap的承载量(HashMap的默认承载量length是16,可以自动变长。在构造HashMap的时候也可以指定一个长度。这个承载量就是上图所描述的数组的长度。)进行逻辑与运算,即 h & (length-1),这样得到的结果就是一个比length小的正数,我们把这个值叫做index。其实这个index就是索引将要插入的值在数组中的位置。第2步那个算法的意义就是希望能够得出均匀的index,这是HashTable的改进,HashTable中的算法只是把key的hashcode与length相除取余,即hash % length,这样有可能会造成index分布不均匀。还有一点需要说明,HashMap的键可以为null,它的值是放在数组的第一个位置。 
4、 我们用table[index]表示已经找到的元素需要存储的位置。先判断该位置上有没有元素(这个元素是HashMap内部定义的一个类Entity,基本结构它包含三个类,key,value和指向下一个Entity的next),没有的话就创建一个Entity

static class Entry implements Map.Entry
{
        final K key;
        V value;
        Entry next;
        final int hash;
        ...//More code goes here
}   

 

每当往hashmap里面存放key-value对的时候,都会为它们实例化一个Entry对象,这个Entry对象就会存储在前面提到的Entry数组table中。现在你一定很想知道,上面创建的Entry对象将会存放在具体哪个位置(在table中的精确位置)。答案就是,根据key的hashcode()方法计算出来的hash值(来决定)。hash值用来计算key在Entry数组的索引。

存储机制分析

原文地址:

http://www.zuidaima.com/share/1850411710188544.htm

HashMap的构造方法: 
无参构造方法:会使用默认的初始容量和加载因子初始化map,默认初始化大小是16,加载因子0.75f。当哈希表中的条目数超出了加载因子与当前容量的乘积时,则要对该哈希表进行 rehash 操作(即重建内部数据结构),从而哈希表将具有大约两倍的桶数。

/**
 * The default initial capacity - MUST be a power of two.
 */
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
/**
 * The load factor used when none specified in constructor.
 */
static final float DEFAULT_LOAD_FACTOR = 0.75f;
public HashMap() {
       this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
}

 

自定义初始化大小

/**
   * Constructs an empty <tt>HashMap</tt> with the specified initial
   * capacity and the default load factor (0.75).
   *
   * @param  initialCapacity the initial capacity.
   * @throws IllegalArgumentException if the initial capacity is negative.
   */
  public HashMap(int initialCapacity) {
      this(initialCapacity, DEFAULT_LOAD_FACTOR);
  }

 

自定义初始化大小和加载因子

/**
     * Constructs an empty <tt>HashMap</tt> with the specified initial
     * capacity and load factor.
     *
     * @param  initialCapacity the initial capacity
     * @param  loadFactor      the load factor
     * @throws IllegalArgumentException if the initial capacity is negative
     *         or the load factor is nonpositive
     */
    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();
    }

 

总结:当 创建 HashMap 时,有一个默认的负载因子(load factor),其默认值为 0.75,这是时间和空间成本上一种折衷:增大负载因子可以减少 Hash 表(就是那个 Entry 数组)所占用的内存空间,但会增加查询数据的时间开销,而查询是最频繁的的操作(HashMap 的 get() 与 put() 方法都要用到查询);减小负载因子会提高数据查询的性能,但会增加 Hash 表所占用的内存空间。我们可以在创建 HashMap 时根据实际需要适当地调整 load factor 的值;如果程序比较关心空间开销、内存比较紧张,可以适当地增加负载因子;如果程序比较关心时间开销,内存比较宽裕则可以适当的减少负载因子。通常情况 下,无需改变负载因子的值。 
HashMap最常用的put方法,代码如下:

/**
    * 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 <tt>key</tt>, or
    *         <tt>null</tt> if there was no mapping for <tt>key</tt>.
    *         (A <tt>null</tt> return can also indicate that the map
    *         previously associated <tt>null</tt> with <tt>key</tt>.)
    */
   public V put(K key, V value) {
       //如果数组为空,初始化
       if (table == EMPTY_TABLE) {
           inflateTable(threshold);
       }
       //如果key为空,则调用putForNullKey进行处理
       if (key == null)
           return putForNullKey(value);
       int hash = hash(key);//计算key的hashcode值
       int i = indexFor(hash, table.length);//计算key在hash表中的索引,此处的table是一个Entry<k,v>数组
       //遍历数组,比较Entry是否一致(hash值相等,即在hash表中的同一位置),并且key值相等,则直接用新的value替换旧的value并返回value,key值不用替换。如果不满足条件,则将key和value添加到i索引处
       for (Entry<K,V> e = table[i]; e != null; e = e.next) {
           Object k;
           if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
               V oldValue = e.value;
               e.value = value;
               e.recordAccess(this);
               return oldValue;
           }
       }

       modCount++;
      //将key和value添加到i索引处
       addEntry(hash, key, value, i);
       return null;
   }

 

上面的put方法中用到了一个重要的内部类HashMap$Entry,每个 Entry 其实就是一个 key-value 对。从上面程序中可以看出:当系统决定存储 HashMap 中的 key-value 对时,完全没有考虑 Entry 中的 value,仅仅只是根据 key 来计算并决定每个 Entry 的存储位置。当决定了 key 的存储位置之后,value 随之保存在那里即可,Entry源码如下:

static class Entry<K,V> implements Map.Entry<K,V> {
       final K key;//key值
       V value;//value值
       Entry<K,V> next;//Entry链指向
       int hash;//key的hash值

       /**
        * Creates new entry.
        */
       Entry(int h, K k, V v, Entry<K,V> n) {
           value = v;
           next = n;
           key = k;
           hash = h;
       }

       public final K getKey() {
           return key;
       }

       public final V getValue() {
           return value;
       }

       public final V setValue(V newValue) {
           V oldValue = value;
           value = newValue;
           return oldValue;
       }

       public final boolean equals(Object o) {
           if (!(o instanceof Map.Entry))
               return false;
           Map.Entry e = (Map.Entry)o;
           Object k1 = getKey();
           Object k2 = e.getKey();
           if (k1 == k2 || (k1 != null && k1.equals(k2))) {
               Object v1 = getValue();
               Object v2 = e.getValue();
               if (v1 == v2 || (v1 != null && v1.equals(v2)))
                   return true;
           }
           return false;
       }

       public final int hashCode() {
           return Objects.hashCode(getKey()) ^ Objects.hashCode(getValue());
       }

       public final String toString() {
           return getKey() + "=" + getValue();
       }

       /**
        * This method is invoked whenever the value in an entry is
        * overwritten by an invocation of put(k,v) for a key k that's already
        * in the HashMap.
        */
       void recordAccess(HashMap<K,V> m) {
       }

       /**
        * This method is invoked whenever the entry is
        * removed from the table.
        */
       void recordRemoval(HashMap<K,V> m) {
       }
   }

 

put方法中调用了一个计算Hash码的方法hash()来返回key的哈希码,这个方法是一个纯粹的数学计算,其方法如下:

final int hash(Object k) {
      int h = hashSeed;
      if (0 != h && k instanceof String) {
          return sun.misc.Hashing.stringHash32((String) k);
      }

      h ^= k.hashCode();

      // 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);
  }

 

对于任意给定的对象,只要它的 hashCode() 返回值相同,那么程序调用 hash(int h) 方法所计算得到的 Hash 码值总是相同的。接下来程序会调用 indexFor(int h, int length) 方法来计算该对象应该保存在 table 数组的哪个索引处。indexFor(int h, int length) 方法的代码如下:

//h为key的hash值,length为数组的长度
static int indexFor(int h, int length) 
{ 
    return h & (length-1); 
}

 

这个方法非常巧妙,它总是通过 h &(table.length -1) 来得到该对象的保存位置,而HashMap底层数组的长度总是2的n次方,这一点可参看前面关于HashMap构造器的介绍。

当length总是2的倍数时,h&(length-1)将是一个非常巧妙的设计:假设 h=5,length=16, 那么h&(length - 1) 将得到5;如果h=6,length=16, 那么h&(length - 1)将得到6 ;如果h=15,length=16, 那么h&(length - 1)将得到15;但是当h=16时 ,length=16时,那么h&(length - 1)将得到0了;当 h=17 时 , length=16 时,那么h&(length - 1) 将得到1了……这样保证计算得到的索引值总是位于 table 数组的索引之内。

从put 方法的源代码可以看出,当程序试图将一个 key-value 对放入 HashMap 中时,程序首先根据该 key 的 hashCode() 返回值决定该 Entry 的存储位置:如果两个 Entry 的 key 的 hashCode() 返回值相同,那它们的存储位置相同。存储位置相同会分为两种情况:

(1).如果这两个 Entry 的 key 通过 equals 比较返回 true,新添加 Entry 的 value 将覆盖集合中原有 Entry 的 value,但 key 不会覆盖。

(2).如果这两个 Entry 的 key 通过 equals 比较返回 false,新添加的 Entry 将与集合中原有 Entry 形成 Entry 链,而且新添加的 Entry 位于 Entry 链的头部——具体说明继续看 addEntry() 方法的说明。

存储位置不同,则将key和value直接添加到i索引处。

addEntyr方法,源码如下:

void addEntry(int hash, K key, V value, int bucketIndex) {
    //如果容量大于阈值,并且索引bucketIndex处的元素不为空       
    if ((size >= threshold) && (null != table[bucketIndex])) {
         resize(2 * table.length);//扩容为原来数组长度的两倍
         hash = (null != key) ? hash(key) : 0;//重新计算key的hash值
         bucketIndex = indexFor(hash, table.length);//重新计算元素在新table中的索引
     }
     //创建新的entry对象并放到table的bucketIndex索引处,并让新的entry指向原来的entry
     createEntry(hash, key, value, bucketIndex);
 }

 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++;
 }

 

上面createEntry方法包含了一个非常优雅的设计:总是将新添加的 Entry 对象放入 table 数组的 bucketIndex 索引处——如果 bucketIndex 索引处已经有了一个 Entry 对象,那新添加的 Entry 对象指向原有的 Entry 对象(产生一个 Entry 链),如果 bucketIndex 索引处没有 Entry 对象,上面程序 e 变量是 null,也就是新放入的 Entry 对象指向 null,也就是Entry内部类中的next属性为null,也就是没有产生 Entry 链。,可以对比Entry类看。

解释几个名词:

桶:对 于 HashMap 及其子类而言,它们采用 Hash 算法来决定集合中元素的存储位置。当开始初始化 HashMap 时,会创建一个长度为 capacity 的 Entry 数组,这个数组里可以存储元素的位置被称为“桶(bucket)”,每个 bucket 都有其指定索引,系统可以根据其索引快速访问该 bucket 里存储的元素。

Entry链:无论何时,HashMap 的每个“桶”只存储一个元素(也就是一个 Entry),由于 Entry 对象可以包含一个引用变量(就是 Entry 构造器的的最后一个参数next)用于指向下一个 Entry,因此可能出现的情况是:HashMap 的 bucket 中只有一个 Entry,但这个 Entry 指向另一个 Entry ——这就形成了一个 Entry 链。下图为我简单的画了一个HashMap的存储结构: 
这里写图片描述

通过Java HashMap的存取方式来学习Hash存储机制 
HashMap最常用的get方法,源码如下:

 public V get(Object key) {
      //如果key为null,则调用getForNullKey获得value
      if (key == null)
          return getForNullKey();
      //否则调用getEntry方法
      Entry<K,V> entry = getEntry(key);

      return null == entry ? null : entry.getValue();
 }

 final Entry<K,V> getEntry(Object key) {
        if (size == 0) {
            return null;
        }
        //计算key的hash值
        int hash = (key == null) ? 0 : hash(key);
        //直接通过key的hash值获取该Entry在数组中的下标,从而获取该Entry对象并遍历entry链,直到找到相等的key,然后取出该key对应的value。
        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;
 }

 

从上面代码中可以看出,如果 HashMap 的每个 bucket 里只有一个 Entry 时,HashMap 可以根据索引、快速地取出该 bucket 里的 Entry;在发生“Hash 冲突”的情况下,单个 bucket 里存储的不是一个 Entry,而是一个 Entry 链,只能按顺序遍历每个 Entry,直到找到想搜索的 Entry 为止——如果恰好要搜索的 Entry 位于该 Entry 链的最末端(该 Entry 是最早放入该 bucket 中),那必须循环到最后才能找到该元素。所以,当 HashMap 的每个 bucket 里存储的 Entry 只是单个 Entry ,也就是没有通过指针产生 Entry 链时,此时的 HashMap 具有最好的性能:当程序通过 key 取出对应 value 时,只要先计算出该 key 的 hashCode() 返回值,在根据该 hashCode 返回值找出该 key 在 table 数组中的索引,然后取出该索引处的 Entry,最后返回该 key 对应的 value 即可。

算是自己学习的Map的网上资料的一个汇总(当是备忘录了吧)。 
附上自己感觉比较好的文档:

http://carmen-hongpeng.iteye.com/blog/1706415#

http://www.oracle.com/technetwork/cn/articles/maps1-100947-zhs.html

http://zhangshixi.iteye.com/blog/672697

http://www.iteye.com/topic/838030

本文转载自:http://blog.csdn.net/u011060103/article/details/51355763

共有 人打赏支持
球球
粉丝 4
博文 225
码字总数 54036
作品 0
石景山
程序员
私信 提问
hashmap实现原理浅析

看了下JAVA里面有HashMap、Hashtable、HashSet三种hash集合的实现源码,这里总结下,理解错误的地方还望指正 HashMap和Hashtable的区别 HashSet和HashMap、Hashtable的区别 HashMap和Hashtab...

商者
2016/03/30
37
0
Java集合浅析

Java集合类框架图 Collection List | 类型 | 数据结构 | 查询速度 | 插入速度 | 是否线程安全 || ArrayList | 数组 | 快 | 慢 | 否 || LinkList | 双向链表,| 慢 | 快 | 否 | Vector 数组 ...

wjk_snail
2016/01/19
86
0
Java系列文章(全)

JVM JVM系列:类装载器的体系结构 JVM系列:Class文件检验器 JVM系列:安全管理器 JVM系列:策略文件 Java垃圾回收机制 深入剖析Classloader(一)--类的主动使用与被动使用 深入剖析Classloader(二...

www19
2017/07/04
0
0
LinkedHashMap浅析

首先明确几点: LinkedHashMap继承在HashMap,非线程安全的 数据存储是通过HashMap存储,自身通过链表存储 LinkedHashMap中Entry继承自HashMap的Entry,扩展了两个字段:before和after:实现...

清尘V
2016/05/08
8
0
2016文章汇总

Java系列: JVM系列:jvm基本结构 JVM系列:java中JVM的原理 JVM系列:解决JVM最大内存设置问题 JVM系列:JVM参数设置、分析 HashMap , HashTable , ConcurrentHashMap 源码比较 从使用到原理学习...

www19
2017/01/03
0
0

没有更多内容

加载失败,请刷新页面

加载更多

AWS的自动部署工具codedeploy 负载均衡器和github

Elastic Load Balancing 提供了三种可用于 CodeDeploy 部署的负载均衡器:Classic Load Balancer、Application Load Balancer 和 Network Load Balancer。 传统负载均衡器 路由和负载均衡在传...

守护-创造
20分钟前
2
0
Docker 使用简介

Docker 是使用 GoLang 开发的开源容器引擎,可以方便的打包开发好的应用,然后分发到任意 linux 主机上。 与传统的虚拟机相比拥有以下优势: 高效的系统资源利用率 由于不需要进行硬件虚拟和...

YanWen
23分钟前
1
0
linux多线程编程,你还在用sleep么?用pthread_cond_timedwait吧

gnal(&cond); pthread_mutex_unlock(&mutex); printf(“Wait for thread to exit\n”); pthread_join(thread, NULL); printf(“Bye\n”); return 0; } 说明(翻译摘要中提供的连接,翻译的不好......

shzwork
31分钟前
1
0
MacOS源码编译安装 PostgreSQL

编译环境 Mac OSX 下只要装了 Xcode 就行,所有编译需要的工具和类库都有了。CentOS 下需要安装下面的软件包。 $ sudo yum install make gcc readline-devel zlib-devel flex bison 如果是从...

FeanLau
41分钟前
2
0
Spring Cloud Alibaba基础教程:Sentinel使用Apollo存储规则

上一篇我们介绍了如何通过Nacos的配置功能来存储限流规则。Apollo是国内用户非常多的配置中心,所以,今天我们继续说说Spring Cloud Alibaba Sentinel中如何将流控规则存储在Apollo中。 使用...

程序猿DD
48分钟前
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部