- 浏览: 341262 次
- 性别:
- 来自: 北京
文章分类
最新评论
-
白色蜻蜓:
...
(转载)新浪微博错误提示代码 -
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 8321.volatile变量 当变量声明为volatile类 ... -
slf4j源码分析
2012-12-11 15:58 5802近期由于想利用应用程序的输出日志做一些应用,了解了下java ... -
HashSet、LinkedHashSet 实现原理
2012-12-07 16:00 1534之前没用过HashSet,听到别人提到HashSet,看了下源 ... -
logback udp appender
2012-11-29 11:44 2398package com.macken; impor ... -
log4j
2012-11-23 11:47 922log4j简要结构图 logback -
ThreadLocal这么回事
2012-11-21 18:04 1369今天线程池实现,看到一个使用ThreadLocal的地方,研 ... -
Java关键字synchronized
2012-08-15 17:57 01、synchronized关键字的作 ... -
HtmlCleaner CleanerProperties 参数配置
2012-07-06 15:34 3013Parameter Default ... -
dom4j读取http xml文件
2012-07-04 14:19 1476使用dom4j读取http xml文件,结合XPATH提取数据 ... -
(转)Filter(过滤器)简介和工作原理
2012-07-04 10:07 1323Filter(过滤器)简介 F ... -
HttpClient实现HTTP文件通用下载类
2012-07-03 15:16 52507import java.io.File; import ... -
Java 解析BT Torrent文件
2012-07-03 14:49 0参考资料: http://www.cesclub.co ... -
URLConnection与HttpClient的对比
2012-07-01 22:00 2644from:http://www.innovation.ch/j ... -
httpclient进化
2012-07-01 21:35 1339httpcomponents与commons-httpclie ... -
(转)HttpClient4.1入门教程
2012-07-01 21:05 0HttpClient简介 1) 百科名片: H ... -
Java操作excel
2012-06-28 13:57 875使用JexcelApi包 maven依赖 <de ... -
Java并发编程之ConcurrentHashMap
2012-06-18 15:10 865http://www.goldendoc.org/2011/0 ... -
正则提起图片地址
2012-06-16 14:07 1009<p><img alt=" ... -
Web-harvest 2.0 Maven 配置
2012-05-08 14:26 1368<project xmlns="htt ... -
htmlparse module导入eclipse
2012-04-28 15:08 927源码地址 https://htmlparser.svn.s ...
相关推荐
深入Java集合学习系列(四): LinkedHashMap的实现原理
在理解了#7 介绍的HashMap后,我们来学习LinkedHashMap的工作原理及实现。首先还是类似的,我们写一个简单的LinkedHashMap的程序: LinkedHashMap<String> lmap = new LinkedHashMap(); lmap.put(语文, 1)...
主要介绍了Java HashMap实现原理的分析,帮助大家更好的理解和使用Java,感兴趣的朋友可以了解下
介绍LinkedHashMap的底层原理 请介绍TreeMap的底层原理 Map和Set有什么区别 ArrayList和LinkedList有什么区别 有哪些线程安全的List 介绍一下ArrayList的数据结构 谈谈CopyOnWriteArrayList的原理 说一说TreeSet和...
Java的LRU算法的基础是LinkedHashMap,LinkedHashMap继承了HashMap,并且在HashMap的基础上进行了一定的改动,以实现LRU算法。 1、HashMap 首先需要说明的是,HashMap将每一个节点信息存储在Entry<
Java的LRU算法的基础是LinkedHashMap,LinkedHashMap继承了HashMap,并且在HashMap的基础上进行了一定的改动,以实现LRU算法。 1、HashMap 首先需要说明的是,HashMap将每一个节点信息存储在Entry结构中。Entry
java基础 1、Arrays.sort实现原理和Collections.sort实现原理。 答:Collections.sort方法底层会调用Arrays.sort...hashtable和hashmap的区别及实现原理,hashmap会问到数组索引,hash碰撞怎么解决 arraylist和linke
该文档主要详细总结了Java集合的相关知识,包括Collection和Map接口、Collection接口的子接口List和Set接口以及具体的实现类、存储原理等;Map接口的子接口HashMap、LinkedHashMap、TreeMap、Properties等
ConcurrentHashMap 的实现原理 线程池原理 深入理解线程通信 交替打印奇偶数 JVM Java 运行时内存划分 类加载机制 OOM 分析 垃圾回收 对象的创建与内存分配 你应该知道的 volatile 关键字 分布式相关 分布式限流 ...
Java集合详解1:一文读懂ArrayList,Vector与Stack使用方法和实现原理 Java集合详解2:Queue和LinkedList Java集合详解3:Iterator,fail-fast机制与比较器 Java集合详解4:HashMap和HashTable Java集合详解5:深入...
Java的数据结构相关的类实现原理,比如LinkedList,ArrayList,HashMap, TreeMap这一类的。以下简单模拟一个数据结构的连环炮。 比如,面试官先问你HashMap是不是有序的? 你肯定回答说,不是有序的。那面试官就会...
ConcurrentHashMap 的实现原理 线程池原理 深入理解线程通信 交替打印奇偶数 JVM Java 运行时内存划分 类加载机制 OOM 分析 垃圾回收 对象的创建与内存分配 你应该知道的 volatile 关键字 分布式相关 分布式限流 ...
ConcurrentHashMap 的实现原理 线程池原理 深入理解线程通信 交替打印奇偶数 JVM Java 运行时内存划分 类加载机制 OOM 分析 垃圾回收 对象的创建与内存分配 你应该知道的 volatile 关键字 分布式相关 分布式限流 ...
Java的集合类总结,包括HashMap、HashSet、HashTable、LinkedHashMap、LinkedHashSet、ArrayList、LinkedList、ConcurrentHashMap的实现原理,很详实,面试的话可以认真看看
主要基于jdk8, 可能会有些特性与jdk7之前不相同, 例如LinkedList LinkedHashMap中的双向列表不再是回环的。 HashMap中的单链表是尾插, 而不是头插入等等, 后文不再赘叙这些差异, 本文目录结构如下: LinkedList 经典...
之前分析过Lru算法的实现方式:HashMap+双向链表,参考链接: 这里主要介绍Android SDK中LruCache缓存算法的实现. 构造函数 LruCache只有一个构造函数,并且有一个必传参数: public LruCache(int maxSize) { if (maxSize...
11.4.2 实现类LinkedHashMap285 11.4.3 实现类TreeMap286 11.4.4 实现类Properties287 11.5 Collections类288 11.6 泛型概述292 11.7 本章习题300 第12章 12.1 理解线程304 12.1.1 什么是多线程304 12.1.2 进程和...
源码分析:ArrayList、Vector、CopyOnWriteArrayList、LinkedList、HashMap、ConcurrentHashMap、LinkedHashMap、WeekHashMap。 线程使用方式、两种互斥同步方法、线程协作、JUC、线程安全、内存模型、锁优化。 运行...
14.7.4 LinkedHashMap类的使用 304 14.7.5 SortedMap接口与TreeMap类 305 14.7.6 映射的遍历 308 14.8 栈在Java中的实现 309 14.8.1 Stack类的使用 309 14.8.2 Deque接口的使用 310 14.8.3 利用栈计算...
1. 目录 1. 2. 目录 .........................................................................................................................................................1 JVM ........................