- 浏览: 346882 次
- 性别:
- 来自: 北京
文章分类
最新评论
-
白色蜻蜓:
...
(转载)新浪微博错误提示代码 -
crzdot:
我也是用ultroiso做的mini启用盘,然后再把iso拷到 ...
centos6.4安装 -
k496229870:
...
libgdx学习之Camera -
DiaoCow:
蛮不错的。
redis命令思维导图 -
kingdelee:
HTTPClient完胜?
URLConnection与HttpClient的对比
看源码可以知道HashMap内部是由一个 Entry[] table组成
Entry的定义如下
static class Entry<K,V> implements Map.Entry<K,V> { final K key; V value; Entry<K,V> next; final int hash; }
key、value
一个hash值,next指向下一个entry对象(后续会说为什么有这个next存在);
HashMap的put方法实现
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; 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; }
根据key对象的hashCode进行哈希,hash方法
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); }
因此,不同key的hash值可能是相同的,所以需要存在next指针指向下一个对象,也就是说对于hash相同的对象,是以链表的形式存储的。
HashMap的实现结构图如下
HashMap的使用建议
在使用HashMap时,最好显示声明HashMap的容量(initialCapacity),以及负载因(loadFactor)
initialCapacity在HashMap初始化时确定数组的大小;
threhold=loadFactor*initialCapacity,确定数组何时扩充容量,扩充容量是现在数组大小的2倍;
initialCapacity 默认大小是16
loadFactor是0.75
也就是说如果你按照以下方式一个HashMap
Map<K,V> map=new HashMap<K,V>();
当put的元素数目大于12的时候,可能就会导致HashMap需要扩容。扩容函数
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); }
看上面代码,resize是新建一个大数组,把原有的数据的entry重新哈希放到新数组中,很是浪费资源。所以在使用HashMap时尽量指定初始化大小;
LinkedHashMap实现原理
LinkedHashMap继承在HashMap,其中对Entry<K,V>对象进行了扩展,定义如下:
private static class Entry<K,V> extends HashMap.Entry<K,V> { // These fields comprise the doubly linked list used for iteration. Entry<K,V> before, after; Entry(int hash, K key, V value, HashMap.Entry<K,V> next) { super(hash, key, value, next); } }在原有HashMap.Entry<K,V>基础上加入了before、after两个指针,那么LinkedHashMap就变成了一个带有双向链表的数组;因此在Iterator时,LinkedHashMap的速度要高于HashMap,而且在Map的容量越大时,区别更明显;
发表评论
-
volatile变量
2013-09-04 10:44 8691.volatile变量 当变量声明为volatile类 ... -
slf4j源码分析
2012-12-11 15:58 5846近期由于想利用应用程序的输出日志做一些应用,了解了下java ... -
HashSet、LinkedHashSet 实现原理
2012-12-07 16:00 1569之前没用过HashSet,听到别人提到HashSet,看了下源 ... -
logback udp appender
2012-11-29 11:44 2440package com.macken; impor ... -
log4j
2012-11-23 11:47 981log4j简要结构图 logback -
ThreadLocal这么回事
2012-11-21 18:04 1441今天线程池实现,看到一个使用ThreadLocal的地方,研 ... -
Java关键字synchronized
2012-08-15 17:57 01、synchronized关键字的作 ... -
HtmlCleaner CleanerProperties 参数配置
2012-07-06 15:34 3080Parameter Default ... -
dom4j读取http xml文件
2012-07-04 14:19 1524使用dom4j读取http xml文件,结合XPATH提取数据 ... -
(转)Filter(过滤器)简介和工作原理
2012-07-04 10:07 1391Filter(过滤器)简介 F ... -
HttpClient实现HTTP文件通用下载类
2012-07-03 15:16 52604import java.io.File; import ... -
Java 解析BT Torrent文件
2012-07-03 14:49 0参考资料: http://www.cesclub.co ... -
URLConnection与HttpClient的对比
2012-07-01 22:00 2729from:http://www.innovation.ch/j ... -
httpclient进化
2012-07-01 21:35 1377httpcomponents与commons-httpclie ... -
(转)HttpClient4.1入门教程
2012-07-01 21:05 0HttpClient简介 1) 百科名片: H ... -
Java操作excel
2012-06-28 13:57 924使用JexcelApi包 maven依赖 <de ... -
Java并发编程之ConcurrentHashMap
2012-06-18 15:10 907http://www.goldendoc.org/2011/0 ... -
正则提起图片地址
2012-06-16 14:07 1048<p><img alt=" ... -
Web-harvest 2.0 Maven 配置
2012-05-08 14:26 1425<project xmlns="htt ... -
htmlparse module导入eclipse
2012-04-28 15:08 995源码地址 https://htmlparser.svn.s ...
相关推荐
在Java编程语言中,`HashMap`、`TreeMap`和`LinkedHashMap`都是`java.util.Map`接口的实现,它们提供了不同的数据存储和访问策略。本文将深入探讨这三种数据结构的特点、工作原理以及适用场景。 1. **HashMap** `...
综上所述,理解HashMap的实现原理对于优化Java程序性能至关重要,尤其是在处理大量数据或并发场景时。在实际应用中,应根据具体需求选择合适的数据结构,例如,如果需要线程安全,可以选择ConcurrentHashMap;如果对...
总的来说,LinkedHashMap 是 HashMap 的一个扩展,通过增加链表结构实现了按照插入顺序或访问顺序迭代的能力。它的内部节点(Entry 类)继承自 HashMap 的 Node 类,并增加了前后指针,形成一个双向链表。通过回调...
HashMap是Java中非常常见的一种数据结构,主要用于存储键值对,其核心原理是通过哈希算法将键映射到数组中的位置来实现快速访问。本文将详细介绍HashMap的底层原理,包括其内部实现结构、关键字段的作用、以及JDK ...
在理解了#7 介绍的HashMap后,我们来学习LinkedHashMap的工作原理及实现。首先还是类似的,我们写一个简单的LinkedHashMap的程序: LinkedHashMap<String> lmap = new LinkedHashMap(); lmap.put(语文, 1)...
**LinkedHashMap的工作原理** LinkedHashMap内部维护了一个双向链表,每个元素既是链表中的节点,也是哈希表中的键值对。在插入新元素时,它会将新元素添加到链表的末尾,并更新哈希表的映射关系。如果选择按照访问...
HashMap的实现原理基于哈希表,它的核心是通过哈希函数将键(key)映射到一个数组的特定位置,从而实现快速访问。本文将深入解析HashMap的put和get操作的内部机制。 首先,HashMap的底层数据结构是一个动态扩容的...
在"深入Java集合学习系列(四):LinkedHashMap的实现原理_尚硅谷_张晓飞.pdf"中,你将深入理解LinkedHashMap的内部双向链表结构及其与HashMap的区别。 总结起来,这个学习系列将帮助你全面理解Java集合框架中的...
然而,HashMap本身并不保证元素的顺序,特别是当涉及到遍历或输出HashMap的内容时,顺序可能会不确定,因为它是基于哈希算法实现的。在某些场景下,我们可能需要对HashMap进行排序,例如按照key的值或key的自然顺序...
这份"java集合PDF汇总"包含了一系列深入学习Java集合的资料,特别是对ArrayList、HashMap和LinkedHashMap这三种常用集合类的实现原理进行了详细解析。 首先,我们来看"深入Java集合学习系列(一):HashMap的实现原理...
6. 使用接口而非实现类:在声明变量时,使用Map而非HashMap,这样在实际运行时可以更灵活地更换其他类型的Map,如LinkedHashMap,以改变元素的排序或性能特性。 CacheManager.java文件可能是一个用于管理缓存的类,...
总之,ArrayList和HashMap是Java集合框架中的重要组件,理解它们的工作原理和适用场景,能帮助我们更有效地处理数据存储和操作。在选择使用哪种数据结构时,应考虑其特性、性能需求以及线程安全性等因素。
Java HashMap 是一种高效的数据结构,它是基于哈希表(散列表)原理实现的,用于存储键值对。HashMap 的核心思想是通过键对象的 `hashCode` 方法计算出一个哈希码,进而确定键值对在数组中的存储位置,即桶(bucket...
HashMap在内部实现上基于哈希表,提供了快速的插入、删除和查找操作,通常时间复杂度为O(1)。 HashMap的工作原理基于哈希函数,当我们将一个键值对放入HashMap时,哈希函数会将键(key)转换为一个哈希码(hash ...
`LinkedHashMap`是Java集合框架中的一个重要组成部分,属于`Map`接口的一个实现类。这个数据结构结合了哈希表(HashMap)和链表的特点,能够在保持元素的键值对存储的同时,保证元素的插入顺序或者按照访问顺序进行...
Linked HashMap的实现原理主要有两个方面:一是链表结构,二是哈希表结构。链表结构是指LinkedHashMap内部采用双向链表来存储元素,哈希表结构是指LinkedHashMap继承自HashMap,使用哈希表来存储元素。...