在Java编程语言中,最基本的结构就是两种,一种是数组,一种是模拟指针(引用),所有的数据结构都可以用这两个基本结构构造,HashMap也一样。当程序试图将多个 key-value 放入 HashMap 中时,以如下代码片段为例:
m.put("a", "rrr1");
m.put("b", "tt9");
m.put("c", "tt8");
m.put("d", "g7");
m.put("e", "d6");
m.put("f", "d4");
m.put("g", "d4");
m.put("h", "d3");
m.put("i", "d2");
m.put("j", "d1");
m.put("k", "1");
m.put("o", "2");
m.put("p", "3");
m.put("q", "4");
m.put("r", "5");
m.put("s", "6");
m.put("t", "7");
m.put("u", "8");
m.put("v", "9");
HashMap 采用一种所谓的“Hash 算法”来决定每个元素的存储位置。当程序执行 map.put(String,Obect)方法 时,系统将调用String的 hashCode() 方法得到其 hashCode 值——每个 Java 对象都有 hashCode() 方法,都可通过该方法获得它的 hashCode 值。得到这个对象的 hashCode 值之后,系统会根据该 hashCode 值来决定该元素的存储位置。源码如下:
- public V put(K key, V value) {
- if (key == null)
- return putForNullKey(value);
- 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;
- //判断当前确定的索引位置是否存在相同hashcode和相同key的元素,如果存在相同的hashcode和相同的key的元素,那么新值覆盖原来的旧值,并返回旧值。
- //如果存在相同的hashcode,那么他们确定的索引位置就相同,这时判断他们的key是否相同,如果不相同,这时就是产生了hash冲突。
- //Hash冲突后,那么HashMap的单个bucket里存储的不是一个 Entry,而是一个 Entry 链。
- //系统只能必须按顺序遍历每个 Entry,直到找到想搜索的 Entry 为止——如果恰好要搜索的 Entry 位于该 Entry 链的最末端(该 Entry 是最早放入该 bucket 中),
- //那系统必须循环到最后才能找到该元素。
- if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
- V oldValue = e.value;
- e.value = value;
- return oldValue;
- }
- }
- modCount++;
- addEntry(hash, key, value, i);
- return null;
- }
上面程序中用到了一个重要的内部接口:Map.Entry,每个 Map.Entry 其实就是一个 key-value 对。从上面程序中可以看出:当系统决定存储 HashMap 中的 key-value 对时,完全没有考虑 Entry 中的 value,仅仅只是根据 key 来计算并决定每个 Entry 的存储位置。这也说明了前面的结论:我们完全可以把 Map 集合中的 value 当成 key 的附属,当系统决定了 key 的存储位置之后,value 随之保存在那里即可.HashMap程序经过我改造,我故意的构造出了hash冲突现象,因为HashMap的初始大小16,但是我在hashmap里面放了超过16个元素,并且我屏蔽了它的resize()方法。不让它去扩容。这时HashMap的底层数组Entry[] table结构如下:
Hashmap里面的bucket出现了单链表的形式,散列表要解决的一个问题就是散列值的冲突问题,通常是两种方法:链表法和开放地址法。链表法就是将相同hash值的对象组织成一个链表放在hash值对应的槽位;开放地址法是通过一个探测算法,当某个槽位已经被占据的情况下继续查找下一个可以使用的槽位。java.util.HashMap采用的链表法的方式,链表是单向链表。形成单链表的核心代码如下:
- 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);
- bsp;
上面方法的代码很简单,但其中包含了一个设计:系统总是将新添加的 Entry 对象放入 table 数组的 bucketIndex 索引处——如果 bucketIndex 索引处已经有了一个 Entry 对象,那新添加的 Entry 对象指向原有的 Entry 对象(产生一个 Entry 链),如果 bucketIndex 索引处没有 Entry 对象,也就是上面程序代码的 e 变量是 null,也就是新放入的 Entry 对象指向 null,也就是没有产生 Entry 链。
HashMap里面没有出现hash冲突时,没有形成单链表时,hashmap查找元素很快,get()方法能够直接定位到元素,但是出现单链表后,单个bucket 里存储的不是一个 Entry,而是一个 Entry 链,系统只能必须按顺序遍历每个 Entry,直到找到想搜索的 Entry 为止——如果恰好要搜索的 Entry 位于该 Entry 链的最末端(该 Entry 是最早放入该 bucket 中),那系统必须循环到最后才能找到该元素。
当创建 HashMap 时,有一个默认的负载因子(load factor),其默认值为 0.75,这是时间和空间成本上一种折衷:增大负载因子可以减少 Hash 表(就是那个 Entry 数组)所占用的内存空间,但会增加查询数据的时间开销,而查询是最频繁的的操作(HashMap 的 get() 与 put() 方法都要用到查询);减小负载因子会提高数据查询的性能,但会增加 Hash 表所占用的内存空间。
相关推荐
我虽然对于垃圾回收器来说是个问题,但我想像了要使用一个对象检查所有其他对象的tilemap冲突。 每个可碰撞对象都有一个带有SAT.box实例的shape属性。 甚至是绘制为圆形的对象。 仅对照对象所在的图块地图检查...
这个资源是关于手动实现golang中map的源码。在这份资源中,你将学习到如何使用Go语言来手动实现一个基本的哈希表数据结构,并将其转化为Go语言中的Map类型。 首先,我们将介绍哈希表的基本概念和原理,包括哈希函数...
直接运行没错误,但是当发布时,访问就错了,提示SecurityError: Error #2048: 安全沙箱冲突:http://localhost:8086/index.swf 不能从 http://www-c8d8bc651c4/ArcGIS/rest/services/zhengzhou/MapServer?f=json ...
charts3中国地图下钻至县级,刚好项目中要用,结合CSDN资源及百度echarts案例,进行修改。基本满足了各类项目在地图上可视化效果。下周后解压到Http服务后进行访问。案,目前CSDN相关内容积分,内容最全的代码案例。
护身符地图编辑器 ... 我们建议您设置一个以免出现依赖冲突的问题。 运行python -m pip install amulet-map-editor来安装库及其所有依赖项。 运行python amulet_map_editor运行程序 笔记 如果您安装了pytho
Map Map对象保存键值对。...•Object 都有自己的原型,原型链上的键名有可能和你自己在对象上的设置的键名产生冲突。 1.Map对象的属性 •size:返回Map对象中所包含的键值对个数 1.Map对象的方法 •
因为当赋值时,为了减少hash 冲突链的长度过长问题,会做map 的扩容以及数据的迁移。而map 的扩容以及数据的迁移也是关注的重点。 数据结构 首先,我们需要重新学习下map实现的数据结构: type hmap struct { ...
本文实例讲述了ES6中Symbol、Set和Map用法。分享给大家供大家参考,具体如下: Symbol 1.Symbol 是 ES6 引入了一种新的原始数据类型,表示独一无二的值。它是 JavaScript 语言的第七种数据类型,前六种分别是:...
./CBSH2 -m instances/lak503d.map -a instances/lak503dmap-100agents-2.agents -o test.csv -t 60 -s 1 -h WDG -r 1 您可以使用以下命令找到所有参数的详细信息和说明: ./CBSH2 --help 执照 CBSH2是根据USC –...
Hbuilder离线打包继承jpush和map有冲突 so 有个不对
用Ogre实现无缝地图用Ogre实现无缝地图.用Ogre实现无缝地图.用Ogre实现无缝地图.
使用Mapbox和Cosmic制作的冲突地图以及使用Highcharts和Plotly制作的数据可视化 React启动器 一个简单直接的入门项目,无需使用create-react应用程序即可创建React应用程序。 在我们创建React应用程序时,为您提供更...
关于 大圆环地图是一种用于可视化飞行路线并计算机场之间距离的工具。 大圆路径(也称为测地线路径)是地球表面或任何其他球体上两点之间的最短... 例如,为军事目的和冲突地区保留的领空。 地球不是一个完美的球体,在
ConcurrentHashMap继承了AbstractMap,实现了ConcurrentMap,Serializable接口,ConcurrentMap又实现了Map接口。ConcurrentHashMap是基于散列表实现的,存储的是Key/Value对,底层使用数组+链表+红黑树+CAS算法实现...
svn最新版中文语言包,使用在windows平台下非常好用。 实时更新,敬请期待
第1章 正则表达式.... 1 1.1 为什么要用正则表达式... 1 1.2 正则表达式入门......1.2.1 正则表达式中元字符的用法......1.2.2 Java中的正则...2.2.3 冲突与冲突的解决... 20 2.2.4 Java中的Map接口... 20 2.3 HashMap. 21
5. 考虑方便记忆,按键尽量取自其英文版词汇,同时兼顾操作方便、避免布局冲突、减少误操作,以及尽量包容不同软件版本。 6. 全套二百余键,不求全记,而求在需要用时能方便。专门制作Excel布局表格,按键分类着色,...
页码: 6 行: -2~-1 错误: 使用命名空间程序员可以避免与库中定义的名字相同而引起无意冲突。 更正: 使用命名空间...错误: map,int>::value_type(anna,1) 更正: map,int>::value_type("Anna",1) .........
解决冲突Laura Kurgan和Frances Negron-Muntaner在哥伦比亚大学空间研究中心提供的2019年Spring冲突城市主义波多黎各研讨会研究项目。 是关于 的几个学生研究项目之一。 冲突解决方案将多个数据集作为决策模型中的层...
HashMap是一种基于哈希表的Map接口实现,主要用于存储键值对。它允许空值和空键。其主要特点是通过键的哈希值存储值,并提供了添加、获取和操作存储值的方法。 HashMap的底层数据结构是由数组和链表组成的。数组是...