文档章节

jdk容器之HashMap

紫韵
 紫韵
发布于 2016/04/07 19:44
字数 1829
阅读 53
收藏 10

一、HashMap简介

    原博客地址:http://www.cnblogs.com/tstd/p/5055286.html

  1. hash就是通过散列算法,将一个任意长度关键字转换为一个固定长度的散列值,由于hash函数是一个压缩映射,所以可能存在不同的关键字进行hash后所得到的hash值相同的现象。

     hash函数定义如下:

  2. 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);
    }
    /**
     * Returns index for hash code h.
     */
    static int indexFor(int h, int length) {
       return h & (length - 1);
    }

    解析:

    1. 首先看第二个函数indexFor,这个函数用于寻找hash值h在一个长度为length的数组中的位置(即下标值),然后将该hash值所对应的元素存储在相应的位置上。

      由于HashMap中定义的数组长度均为2的幂的形式,而2^n-1表示为2进制时的形式为01....1(1个0后面n个1的形式),所以通过h&(length-1),可以将h映射到0~(length-1)之间的数,达到h%length一样的效果,却拥有比h%length更高的效率;

    2. 再看hash函数,由于h的低位相同(尤其是等于length位数的部分)时,经过hash后冲突的概率比较大,所以在hash函数中给h中的各个位加入了一些随机性,从而尽可能降低冲突;

  3. HashMap的底层是用一个Entrry数组实现的,通过indexFor函数计算hash值为h的元素在一个长度为length的Entry数组中的位置,当出现冲突时,将hash值相同的元素以一个单向链表的形式存储在Entry数组的同一位置,并且最先存储的元素位于链表尾部,最后到达的元素位于链表头。也就是说HashMap的底层结构是一个数组,而数组的元素是一个单向链表。当存储一个key=null的元素时,HashMap默认将该元素置于Entry[0]的位置。

  4. Entry是HashMap的内部类,它继承了Map中的Entry接口,它定义了键(key),值(value),和下一个节点的引用(next),以及hash值。

  5. HashMap中定义了初始容量、加载因子、阈值和最大容量等参数。容量即HashMap中Entry数组所能包含的元素数;初始容量为16,即默认最小容量为16,使用时可以通过含参构造函数构造一个满足用户所需大小的HashMap;加载因子和阈值主要用于定义扩容临界值(阈值=容量*加载因子),当已使用容量达到阈值时,将会扩容;最大容量即默认HashMap所能扩容达到的最大大小,为2^30。

    注意:

    1. HashMap进行扩容时,数组长度发生了变化,原本在同一链表中的元素现在可能并不在同一链表中,所以需要对数组中的每一个元素都重新计算位置,并存储到新数组中,这是一个非常耗时的操作,所以如果事先能够预知需要使用的HashMap的长度的话,最好将长度设置为所需大小,这样可以减少时间消耗,提高效率;

    2.  默认加载因子=0.75,但可以根据需要自己设置一个恰当的加载因子。加载因子越大,数组填充得越满,空间利用率越高,但这样的话可能会增大冲突机率,影响查询效率;而加载因子过小的话,则会造成空间上的浪费。所以需要通过设置一个有效地加载因子,在时空这两者间寻找一个平衡点。

二、HashMap的增删改查

  1. 构造方法

    HashMap有4个构造方法

  2. //构造一个指定初始容量和加载因子的HashMap
    public HashMap( int initialCapacity, float loadFactor)   
    //构造一个指定初始加载容量和使用默认加载因子(0.75)的HashMap
    public HashMap( int initialCapacity)
    //构造一个使用默认初始容量(16)和默认加载因子(0.75)的HashMap
    public HashMap()
    //构造一个指定map的HashMap,所创建HashMap使用默认加载因子(0.75)和足以容纳指定map的初始容量
    public HashMap(Map<? extends K, ? extends V> m)

           当使用指定初始容量的构造函数创建HashMap时,所得到的HashMap的实际容量是大于指定容量的最小的2的幂次方,也就是说,无论使用何种构造函数,最终所得到的HashMap的容量均为2的幂

  3. 向HashMap中增加元素

  4. HashMap中增加元素的方法和修改元素的方法相同,均为public V put(K key, V value),具体操作流程为:

    1. 计算hash = hash(key.hashCode()),得到键值key的hash值

    2. 计算index = indexFor(hash,table.length),得到该元素在数组中的位置

    3. 取得index位置的链表,遍历链表,若链表中包含hash和key值均相同的元素,则用新的value值替换原有的value值,返回原value值;否则在该链表头新增一个Entry节点,将该元素存入新建的Entry节点中,并返回null;

        注意:在新增Entry节点时,数组大小会加1,当size>阈值时,将调用resize(2*table.length)方法扩容,也就是说若新增节点时,数组大小达到了扩容阈值,则会将原数组扩大一倍。数组扩容时需要通过遍历对原数组中的所有元素重新计算下标值,并添加到新数组相应的位置,该算法比较耗时,所以在使用HashMap时若能提前预知数组容量,则最好预设初始容量。

  5. 从 HashMap中删除元素

    HashMap中删除元素的方法为public V remove(Object key),即根据元素的key值删除该元素,并返回所删除元素的value值

    1. 计算hash = hash(key.hashCode()),得到键值key的hash值

    2. 计算index = indexFor(hash,table.length),得到该元素在数组中的位置

    3. 取得该位置处的第一个链表节点

    4. 遍历该链表,找到key所在的位置,若key位于链表头,则将key节点的next赋值给table[index],否则,将key的下一节点赋值给key的上一节点

  6. 从 HashMap中查找元素

  7.         从HashMap中查找元素的方法为public V get(Object key),该方法通过遍历HashMap,比较是否存在(e.hash == hash && ((k = e.key) == key || key.equals(k)))的元素,若存在,返回该元素的value值,否则,返回null

  8. HashMap中是否包含键为key或值为value的元素

        查询HashMap中是否包含某一键key或某一值value的元素时,均需要遍历数组进行查找。但是针对key进行查找时,可以通过hash函数计算出key所在的位置,从而只需要遍历该位置处的链表即可。而针对value进行查找时,需要遍历整个数组。所以针对key进行查找的效率要高于针对value进行查找的效率。

© 著作权归作者所有

紫韵
粉丝 4
博文 21
码字总数 34323
作品 0
武汉
私信 提问
Java 容器 & 泛型:一、认识容器

Writer:BYSocket(泥沙砖瓦浆木匠) 微博:BYSocket 豆瓣:BYSocket 容器是Java语言学习中重要的一部分。泥瓦匠我的感觉是刚开始挺难学的,但等你熟悉它,接触多了,也就“顺理成章”地知道...

泥沙砖瓦浆木匠
2015/03/13
518
2
HashMap 相关面试题及其解答

Q:HashMap 的数据结构? A:哈希表结构(链表散列:数组+链表)实现,结合数组和链表的优点。当链表长度超过 8 时,链表转换为红黑树。 transient Node[] table; Q:HashMap 的工作原理? ...

TinyDolphin
2017/11/21
0
0
java容器学习

java容器: 容器,顾名思义,就是用来存放东西的道具,但是在我们程序开发中容器的概念就是用来存在我们数据对象的引用。 往常的数组存储,由于数组开始的长度已经指定,开发过程中不能随意修...

四月李
2015/12/17
152
0
Java容器 - HashMap(2)

(没写.....挖个坑 主要是整理下高并发的情况下HashMap的问题,他为什么不是线程安全的 首先我们来看一个在JDK8中HashMap的resize 方法 1.Hashmap在插入元素过多的时候需要进行Resize,Resiz...

蠢廿
2017/11/16
0
0
jdk1.6的集合源码阅读之Collection接口

我们知道java容器类类库的用途是“保存对象”,容器最顶层分为两个Collection和Map,其余的都是继承这连个接口,Collection存储一个独立元素的序列,下面有List 、Set、Queue,而Map主要存储...

双月通天
2016/08/23
13
0

没有更多内容

加载失败,请刷新页面

加载更多

RxJava进行单元测试的方式

@Test public void completeTask_retrievedTaskIsComplete() { // Given a new task in the persistent repository final Task newTask = new Task(TITLE, ""); ......

SuShine
24分钟前
5
0
正则表达式大全

检验手机号码 # 要求:手机号码必须为11位数字,以1开头,第二位为1或5或8。import redef verify_mobile(): mob = input("请输入手机号码:") ret = re.match(r"1[358]\d{9}", m......

彩色泡泡糖
28分钟前
5
0
QT之border-image属性

一、border-image的兼容性 border-image可以说是CSS3中的一员大将,将来一定会大放光彩,其应用潜力真的是非常的惊人。可惜目前支持的浏览器有限,仅Firefox3.5,chrome浏览器,Safari3+支持...

shzwork
29分钟前
6
0
Kubernetes Operator简易教程

1. 安装operator-sdk //安装 operator-sdk$ apt-get install operator-sdk.....$ operator-sdk versionoperator-sdk version: v0.7.0$ go versiongo version go1.11.4 darwin/amd64 2......

Robotcl_Blog
29分钟前
5
0
再谈DAG任务分解和Shuffle RDD

1、DagScheduler分析 DagScheduler功能主要是负责RDD的各个stage的分解和任务提交。Stage分解是从触发任务调度过程的finalStage开始倒推寻找父stage,如果父stage没有提交任务则循环提交缺失...

守望者之父
35分钟前
4
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部