文档章节

HashMap原理

不羁青年
 不羁青年
发布于 2015/08/07 13:06
字数 2146
阅读 29
收藏 1

原理

HashMap实现哈希表 Map 接口,提供了所有可选的映射操作并允许使用 null 值和 null 键。HashMap 与 Hashtable 的区别在于HashMap非同步和允许使用 null 。HashMap不能保证读取顺序与插入顺序一致,即无序性。

HashMap的数据结构使用链地址法来处理哈希冲突;链地址法解决冲突的做法是:如果哈希表空间为 0 ~ m - 1 ,那么设置一个由 m 个指针分量组成的一维数组 table[ m ](下面我们称数据的元素为'桶'), 凡哈希地址为 i 的数据元素都插入到头指针为 table[ i ] 的链表中。这种方法适合于冲突比较严重的情况。 例如设有 8 个元素 { a,b,c,d,e,f,g,h } ,采用某种哈希函数得到的地址分别为: {0 , 2 , 4 , 1 , 0 , 8 , 7 , 2} ,当哈希表长度为 10 时,采用链地址法解决冲突的哈希表如下图所示。


closehash

因此由上图可以知道,当所有的元素都能均匀的分布在各个桶中时,hashMap的基本操作都可以在确定时间内完成。迭代器遍历集合的耗时与HashMap的容量capacity(桶)以及key-value键值对的个数成正比。因此在迭代性能要求高的场景,我们应该把容量capacity设大一点,或者把加载因子load factor设低点。

对于HashMap,有两个参数直接影响着其性能:初始容量initial capacity和加载因子load factor.容量capacity指的就是hash table的桶个数,而初始容量init capacity指的就是hash table创建时的容量,容量随着key-value键值的增加可能会改变。加载因子load factor则是衡量hash table在当前容量capacity下可以保存的key-value键值对的最大程度。当key-value键值对的个数超过load factor与capacity的积时,hash table将进行rehash内部数据结构重构操作;此时,重构后hashtable的桶数量大约是原来数量的两倍。

默认情况下,hashMap的加载因子load factor值是0.75,这在时间与空间开销方面是一个较好的折中方案。该值过高可以减少内存的开销,但会增加查找的时间。因此在设置HashMao的 init capacity时,我们需要认着地考虑key-value键值对可能存在的数量,之后设定合理的load factor,以便减少rehash的操作次数。如果key-value键值对的最大数量小于init capacity与load factor的积,那么不会发生rehash操作。

值得注意的是,hashMap是非线程安全的,因此如果多个线程并发访问hashMap并至少一个线程对map进行结构更改时(结构性更改的操作包括adds或者delete操作,但改变key对应的值不算结构性改变操作。),我们就需要在外部进行同步操作。我们可以在hashMap创建时对其进行支持同步操作的封装,比如:

Map m = Collections.synchronizedMap(new HashMap(...));

另外,HashMap的"集合视图方法"(如entrySet())所返回的迭代器都是快速失败:在迭代器创建之后,除了通过迭代器自身的 remove 或 add方法外,其他HashMap的方法在结构上对映射进行修改的行为,都将导致迭代器抛出 ConcurrentModificationException。因此在并发环境下,如果进行结构修改,迭代器快速失败可以及时制止状态的不一致性。然而值得注意的是,迭代器的快速失败只是在不同步的并发修改时,尽最大努力抛出异常,因此我们不能依赖这个异常来处理并发场景,合理的用法是用来发现bug.


实现

上面详细介绍了HashMap的原理,在本节通过代码的形式对原理进行诠释。

首先看下HashMap的主要属性:


static final int DEFAULT_INITIAL_CAPACITY = 16;//默认的初始化容量,值得注意的是,該值必须是2的n次方

    static final float DEFAULT_LOAD_FACTOR = 0.75f;//默认的加载因子的值

    transient Entry[] table;//hash table,即桶,个数必须是2的n次方;注意其类型是transient(transient作用)

    transient int size;//key-value键值对个数

    int threshold;//capacity * load factor,触发rehash的阀值

    transient volatile int modCount;//记录HashMap发生结构性修改的次数,該值会触发迭代器视图的快速失败机制;该属性的类型为volatile,这样确保并发现,线程间的可见性。

下面继续分析HashMap的有参构造函数:


  public HashMap(int initialCapacity, float loadFactor) {
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal initial capacity: " +
                                               initialCapacity);
        if (initialCapacity > MAXIMUM_CAPACITY)
            initialCapacity = MAXIMUM_CAPACITY; //MAXIMUM_CAPACITY = 1 << 30;
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal load factor: " +
                                               loadFactor);

        int capacity = 1;
        while (capacity < initialCapacity)
            capacity <<= 1; //找到一个大于initcapacity的2的n次方整数,为什么一定要2的n方呢?下面会介绍

        this.loadFactor = loadFactor;
        threshold = (int)(capacity * loadFactor);//计算出触发rehash的阀值
        table = new Entry[capacity];
        init();
    }

有参构造函数非常简单,主要就是设置合适的capacity以及计算出rehash阀值。接着继续分析HashMap的存取操作;


1、put操作:

 public V put(K key, V value) {
        if (key == null)//如果为null,则放在第一个桶
            return putForNullKey(value);
        int hash = hash(key.hashCode());//调用key的hashcode()来计算hash值
        int i = indexFor(hash, table.length);//根据hash值与桶个数计算出索引值,即在哪个桶里面
        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++;//Entry为null,执行add操作,即结构性修改,modCount加1
        addEntry(hash, key, value, i);//包访问权限
        return null;
    }

从代码中可以知道,put方法根据key的hashCode重新计算hash值,之后再根据hash值得到这个元素在桶数组中的位置;如果对应桶上的链表已存在对应的key,那么把旧值替换。如果key找不到,说明元素不存在,则执行addEntry进行插入操作:

 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);
        if (size++ >= threshold)
            resize(2 * table.length);}

addEntry方法首先获取bucketIndex出的Entry,之后将新建的Entry放入bucketIndex处,并使新的Entry指向原来的entry;如果key-value键值对的个数超过了阀值,则进行rehash操作。

下面继续介绍HashMap的两个非常有意思并且很重要的函数--hash与IndexFor:

首先看


static int indexFor(int h, int length) {
        return h & (length-1);
    }

在前面已经多个地方提及到HashMap的capacity(即桶个数)总是2的n次方,现在就是揭秘的时候了....capacity-1后,其二进制为一系列1,如8,二进制为1000,8-1=0111因此通过 h & (table.length -1) 可以确定时间得到该对象的保存位置,这是HashMap在速度上的优化。



  static int hash(int h) {
        h ^= (h >>> 20) ^ (h >>> 12);
        return h ^ (h >>> 7) ^ (h >>> 4);
    }

这个方法更有意思,为什么呢?举个例子,假设capacity=8,8-1=0111,参数h=61440=1111 0000 0000 0000,运算后,hash=1111 1110 1110 1111;那么执行IndexFor方法后,返回7(二进制0111);假如不执行hash()方法直接IndexFor,那么所有大于7的hash得到的索引都是0。话说到这里,大家应该知道问什么这么干的原因了吧,让"1"变的均匀一点,这样hash才能均匀分布。



2、get操作


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

首先计算key的hashCode,找到桶数组中对应位置的entry元素,之后通过key的equals方法在entry链表中找到相应的元素。



下面继续分析HashMap的rehash操作:


  void resize(int newCapacity) {
        .........
        Entry[] newTable = new Entry[newCapacity];
        transfer(newTable);
        table = newTable;
        threshold = (int)(newCapacity * loadFactor);
    }
  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;
                    int i = indexFor(e.hash, newCapacity);
                    e.next = newTable[i];
                    newTable[i] = e;
                    e = next;
                } while (e != null);
            }
        }
    }

从代码可以知道rehash是一个非常耗时的操作,原数组中的数据需重新hash计算并计算出在新桶数组中的索引位置;所以如果我们能确定HashMap中元素的个数,那么可以预设好加载因子与initcapacity来提高HashMap的性能。


 Technorati : HashMap原理  
Del.icio.us : HashMap原理  
Zooomr : HashMap原理  
Flickr : HashMap原理

© 著作权归作者所有

不羁青年
粉丝 4
博文 10
码字总数 12914
作品 0
海淀
程序员
私信 提问
常见面试题——HashMap工作原理的介绍!

HashMap的工作原理是近年来常见的Java面试题。几乎每个Java程序员都知道HashMap,都知道哪里要用HashMap,知道HashTable和HashMap之间的区别,那么为何这道面试题如此特殊呢?是因为这道题考...

欧阳海阳
2018/06/24
0
0
为什么要学习HashMap的底层原理?

本文转载自公众号 码农翻身 上周发了一篇文章《漫画:什么是HashMap?》,引起了不少人的讨论,有一个人的留言引发了我的思考:“作为一个程序员, 真的有必要学习这些底层原理吗? 我会用了...

bjweimengshu
2017/12/03
0
0
HashMap 工作原理

HashMap的工作原理是近年来常见的Java面试题。几乎每个Java程序员都知道HashMap,都知道哪里要用HashMap,知道Hashtable和HashMap之间的区别,那么为何这道面试题如此特殊呢?是因为这道题考...

The_flying_pig
2017/09/19
0
0
HashMap的工作原理【文字版】

HashMap的工作原理是近年来常见的Java面试题。几乎每个Java程序员都知道HashMap,都知道哪里要用HashMap,知道Hashtable和HashMap之间的区别,那么为何这道面试题如此特殊呢?是因为这道题考...

半夏alvin
2016/01/07
33
0
详解 Java 8 HashMap 实现原理

HashMap 是 Java 开发过程中常用的工具类之一,也是面试过程中常问的内容,此篇文件通过作者自己的理解和网上众多资料对其进行一个解析。作者本地的 JDK 版本为 64 位的 1.8.0_171。参考资料...

☆★傲天★☆
2018/08/17
0
0

没有更多内容

加载失败,请刷新页面

加载更多

《Designing.Data-Intensive.Applications》笔记 四

第九章 一致性与共识 分布式系统最重要的的抽象之一是共识(consensus):让所有的节点对某件事达成一致。 最终一致性(eventual consistency)只提供较弱的保证,需要探索更高的一致性保证(stro...

丰田破产标志
今天
4
0
docker 使用mysql

1, 进入容器 比如 myslq1 里面进行操作 docker exec -it mysql1 /bin/bash 2. 退出 容器 交互: exit 3. mysql 启动在容器里面,并且 可以本地连接mysql docker run --name mysql1 --env MY...

之渊
今天
6
0
python数据结构

1、字符串及其方法(案例来自Python-100-Days) def main(): str1 = 'hello, world!' # 通过len函数计算字符串的长度 print(len(str1)) # 13 # 获得字符串首字母大写的...

huijue
今天
4
0
OSChina 周日乱弹 —— 我,小小编辑,食人族酋长

Osc乱弹歌单(2019)请戳(这里) 【今日歌曲】 @宇辰OSC :分享娃娃的单曲《飘洋过海来看你》: #今日歌曲推荐# 《飘洋过海来看你》- 娃娃 手机党少年们想听歌,请使劲儿戳(这里) @宇辰OSC...

小小编辑
今天
989
11
MongoDB系列-- SpringBoot 中对 MongoDB 的 基本操作

SpringBoot 中对 MongoDB 的 基本操作 Database 库的创建 首先 在MongoDB 操作客户端 Robo 3T 中 创建数据库: 增加用户User: 创建 Collections 集合(类似mysql 中的 表): 后面我们大部分都...

TcWong
今天
40
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部