1、HashMap
HashMap是Map接口最常见的实现,HashMap是非线程安全的,其内部实现是一种基于一个数组和链表的结合体,如下table为HashMap中存储数据的字段:
transient Entry[] table;
static class Entry<K,V> implements Map.Entry<K,V> { final K key; V value; Entry<K,V> next; final int hash; ...... }
上面的Entry就是数组中的元素,它持有一个指向下一个元素的引用,这就构成了链表。
加载因子:
final float loadFactor;
默认加载因子:
static final float DEFAULT_LOAD_FACTOR = 0.75f;
默认容量:
static final int DEFAULT_INITIAL_CAPACITY = 16;
最大容量:
static final int MAXIMUM_CAPACITY = 1 << 30;
实际扩展容量边界:
int threshold;
当实际数据大小超过threshold时,HashMap会将容量扩容,threshold=容量*加载因子
public HashMap(int initialCapacity, float loadFactor) { if (initialCapacity < 0) throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity); if (initialCapacity > MAXIMUM_CAPACITY) initialCapacity = MAXIMUM_CAPACITY; if (loadFactor <= 0 || Float.isNaN(loadFactor)) throw new IllegalArgumentException("Illegal load factor: " + loadFactor); // Find a power of 2 >= initialCapacity int capacity = 1; while (capacity < initialCapacity) capacity <<= 1; this.loadFactor = loadFactor; threshold = (int)(capacity * loadFactor); table = new Entry[capacity]; init(); }
HashMap的初始容量为capacity而不是参数initialCapacity:
int capacity = 1; while (capacity < initialCapacity) capacity <<= 1;//左移并赋值 table = new Entry[capacity];
如果执行new HashMap(9,0.75);那么HashMap的初始容量是16,而不是9。
当 我们往hashmap中put元素的时候,先根据key的hash值得到这个元素 在数组中的位置(即下标),然后就可以把这个元素放到对应的位置中了。如果这个元素所在的位子上已经存放有其他元素了,那么在同一个位子上的元素将以链表 的形式存放,新加入的放在链头,最先加入的放在链尾。从hashmap中get元素时,首先计算key的hashcode,找到数组中对应位置的某一元 素,然后通过key的equals方法在对应位置的链表中找到需要的元素。如果每个位置上的链表只有一个元素,那么 hashmap的get效率将是最高的。
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; }
HashMap充许key为null,put对象时,对于key为null的情况,HashMap的做法为获取Entry数组的第一个Entry对象,并基于Entry对象的next属性遍历,当找到了其中的Entry对象的key为null时,则将其中value赋值为新的value然后返回,如果没有key为null的Entry,则增加一个Entry对象:
private V putForNullKey(V value) { for (Entry<K,V> e = table[0]; e != null; e = e.next) { if (e.key == null) { V oldValue = e.value; e.value = value; e.recordAccess(this); return oldValue; } } modCount++; addEntry(0, null, value, 0); return null; }
hashmap 中要找到某个元素,需要根据key的hash值来求得对应数组中的位 置。如何计算这个位置就是hash算法。前面说过hashmap的数据结构是数组和链表的结合,所以我们当然希望这个hashmap里面的元素位置尽量的 分布均匀些,尽量使得每个位置上的元素数量只有一个,那么当我们用hash算法求得这个位置的时候,马上就可以知道对应位置的元素就是我们要的,而不用再 去遍历链表。
所以我们首先想到的就是把hashcode对数组长度取模运算,这样一来,元素的分布相对来说是比较均匀的。但是,“模”运算的消耗还是比较大的,能不能找一种更快速,消耗更小的方式那?java中时这样做的:
static int indexFor(int h, int length) { return h & (length-1); }HashMap的数组长度永远都是2的n次方,数组的长度-1的二进制永远全部都是1,再与key的hashcode值做 一次“与”运算 (&)。看上去很简单,其实比较有玄机。比如数组的长度是2的4次方,那么hashcode就会和2的4次方-1做“与”运算。很多人都有这个疑 问,为什么hashmap的数组初始化大小都是2的次方大小时,hashmap的效率最高,我以2的4次方举例,来解释一下为什么数组大小为2的幂时 hashmap访问的性能最高。
所以说,当数组长度为2的n次幂的时候,不同的key算得得index相同的几率较小,那么数据在数组上分布就比较均匀,也就是说碰撞的几率小,相对的,查询的时候就不用遍历某个位置上的链表,这样查询效率也就较高了。
说到这里,我们再回头看一下hashmap中默认的数组大小是多少,查看源代码可以得知是16,为什么是16,而不是15,也不是20呢,看到上面 annegu的解释之后我们就清楚了吧,显然是因为16是2的整数次幂的原因,在小数据量的情况下16比15和20更能减少key之间的碰撞,而加快查询 的效率。 所以,在存储大容量数据的时候,最好预先指定hashmap的size为2的整数次幂次方。就算不指定的话,也会以大于且最接近指定值大小的2次幂来初始 化的,代码如下(HashMap的构造方法中):
int capacity = 1; while (capacity < initialCapacity) capacity <<= 1;
在数组某个位置的对象可能并不是唯一的,它是一个链表结构,根据哈希值找到链表后,还要对链表遍历,找出key相等的对象,替换它,并且返回旧的值:
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; } }
如果遍历完了该位置的链表都没有找到有key相等的,那么将当前对象增加到链表的表头去:
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); }
当 hashmap中的元素越来越多的时候,碰撞的几率也就越来越高(因为数组的长度是固定的),所以为了提高查询的效率,就要对hashmap的数组进行 扩容,数组扩容这个操作也会出现在ArrayList中,所以这是一个通用的操作,很多人对它的性能表示过怀疑,不过想想我们的“均摊”原理,就释然了, 而在hashmap数组扩容之后,最消耗性能的点就出现了:原数组中的数据必须重新计算其在新数组中的位置,并放进去,这就是resize。
那么hashmap什么时候进行扩容呢?当put一个元素时,如果达到了容量限制,也就是threshold的值,数组大小*loadFactor,就会进行数组扩容,新的容量永远是原来的2倍:
if (size++ >= threshold) resize(2 * table.length);
loadFactor 的 默认值为0.75,也就是说,默认情况下,数组大小为16,那么当hashmap中元素个数超过16*0.75=12的时候,就把数组的大小扩展为 2*16=32,即扩大一倍,然后重新计算每个元素在数组中的位置,而这是一个非常消耗性能的操作,所以如果我们已经预知hashmap中元素的个数,那 么预设元素的个数能够有效的提高hashmap的性能。比如说,我们有1000个元素new HashMap(1000), 但是理论上来讲new HashMap(1024)更合适,不过上面annegu已经说过,即使是1000,hashmap也自动会将其设置为1024。 但是new HashMap(1024)还不是更合适的,因为0.75*1000 < 1000, 也就是说为了让0.75 * size > 1000, 我们必须这样new HashMap(2048)才最合适,既考虑了&的问题,也避免了resize的问题。
2、TreeMap
TreeMap是一个支持排序的Map实现,是基于红黑树来实现的,TreeMap是非线程安全的。
3、HashTable
HashTable也是Map接口的一个实现,它是线程安全的,跟HashMap的主要区别有下面几点:
3.1 历史原因,Hashtable是基于陈旧的Dictionary类的,HashMap是Java 1.2引进的Map接口的一个实现
3.2 HashTable是线程安全的,HashMap是非线程安全的
3.3 在HashMap中,null可以作为键 ,这样的键只有一个;可以有一个或多个键所对应的值为null。当get()方法返回null值时,即可以表示 HashMap中没有该键,也可以表示该键所对应的值为null。因此,在HashMap中不能由get()方法来判断HashMap中是否存在某个键, 而应该用containsKey()方法来判断。HashTable中key和value都不能为null。
public synchronized V put(K key, V value) { // Make sure the value is not null if (value == null) { throw new NullPointerException(); } // Makes sure the key is not already in the hashtable. Entry tab[] = table; int hash = key.hashCode();//key为空将抛出异常 int index = (hash & 0x7FFFFFFF) % tab.length; for (Entry<K,V> e = tab[index] ; e != null ; e = e.next) { if ((e.hash == hash) && e.key.equals(key)) { V old = e.value; e.value = value; return old; } } modCount++; if (count >= threshold) { // Rehash the table if the threshold is exceeded rehash(); tab = table; index = (hash & 0x7FFFFFFF) % tab.length; } // Creates the new entry. Entry<K,V> e = tab[index]; tab[index] = new Entry<K,V>(hash, key, value, e); count++; return null; }
3.4 HashTable使用Enumeration,HashMap使用Iterator。
3.5 HashTable中hash数组默认大小是11,增加的方式是 old*2+1。HashMap中hash数组的默认大小是16,而且一定是2的指数。
3.6 哈希值的使用不同,HashTable直接使用对象的hashCode ,代码是这样的:
int hash = key.hashCode(); int index = (hash & 0x7FFFFFFF) % tab.length;
而HashMap重新计算hash值,而且用与代替求模 :
static int hash(int h) { h ^= (h >>> 20) ^ (h >>> 12); return h ^ (h >>> 7) ^ (h >>> 4); } static int indexFor(int h, int length) { return h & (length-1); }
HashMap经验:
由于HashMap扩容会影响性能,在已经知道Map大小的情况下,实例化Map时最好要指定其大小,但不是直接指定,因为Map扩容时其容量并没有满,而是到其容量乘加载因子(0.75),所以这里指定其容量其是用已知的大小除以加载因子,但这里也不要除以.075,最好是除以0.7,这样能确保结果大于除以0.75的。
如把一个List里的元素全部放到HashMap里时:
HashMap<String,Foo> map; void addObjects(List<Foo> input){ map = new HashMap<String, Foo>(); for(Foo f: input){ map.put(f.getId(), f); } }
优化后:
HashMap<String,Foo> _map; void addObjects(List<Foo> input){ map = new HashMap<String, Foo>((int)Math.ceil(input.size() / 0.7)); for(Foo f: input){ map.put(f.getId(), f); } }
相关推荐
Java集合框架中的Map接口表示一种键值对(key-value)的数据结构,其中每个元素都包含一个唯一的键和对应的值。在Map中,每个键必须是唯一的,而值可以重复。Map接口提供了一些方法来实现基本的键值对操作,例如添加...
Java基础知识汇总之集合框架List、Map、Set接口及其子类综合对比
xmind格式的Java集合框架学习导图,包括Collection接口/Map接口以及具体实现类。 同样包含大厂面试题,也在导图中有所体现。 能学到什么: 更加成体系的知识框架,更加全面的、系统的知识。 思维导图: 思维导图具有...
Java集合框架常见面试题 剖析⾯试最常⻅问题之 Java 集合框架 包含以下几个模块: 1、集合概述 2、Collection子接口之List 3、Collection子接口之Set 4、Map接口 5、Collection工具类 6、其他重要问题
java集合框架 3.6. LinkedHashSet类 4. Map接口 4.1. Map.Entry接口 4.2. SortedMap接口 4.3. AbstractMap抽象类 4.4. HashMap类和TreeMap类 4.4.1. HashMap类 4.4.2. TreeMap类 4.5. LinkedHashMap类 4.6. ...
Java集合框架汇总 1.集合框架结构图 1 2.两种特殊的Java容器类List和Set分析 2 3. Collection 接口: 2 4.Iterator 接口: 3 5.List接口: 3 5.1 LinkedList类: 5 5.2 ArrayList类: 5 6.Set接口: 5 7.Map...
农业信息系统开发
本文档先从整体介绍了Java集合框架包含的接口和类,然后总结了集合框架中的一些...Java的集合类主要由两个接口派生而出:Collection和Map,Collection和Map是Java集合框架的根接口,这两个接口又包含了一些接口或实现类
超全Java集合框架讲解 - 超全Java集合框架讲解 - 集合框架总览 - Iterator Iterable ListIterator - Map 和 Collection 接口 - Map 集合体系详解 - HashMap - LinkedHashMap - TreeMap - WeakHashMap - ...
但是,在“集合框架”中,接口 Map 和 Collection 在层次结构没有任何亲缘关系,它们是截然不同的。这种差别的原因与 Set 和 Map 在 Java 库中使用的方法有关。Map 的典型应用是访问按关键字存储的值。它支持一系列...
Koloboke是一个精心设计的java集合框架,相比JDK的设计更加专业和高效。支持JDK6 ,采用Apache 2许可证。Koloboke兼容所有的原始的集合扩展基本的接口(Collection, Set, Map)。示例代码:@KolobokeMap @...
16、JAVA集合框架之Map接口、HashMap类、Trelap类、Hashtable类 17、JAVA异常Exception 18、JAVA线程之基础介绍 19、I0流之基本简介 20、I0流之字符流、字节流、转换流、缓冲流、对象流 21,I0流之HIO
“集合框架”(Collections Framework)提供了一组精心设计的接口和类,它们以单个单元即集合的形式存储和操作数据组 。对于计算机科学数据结构课程中学到的许多抽象数据类型如映射(map)、集(set)、列表(list)...
Java 集合框架的基础接口有哪些? 4. 为何 Collection 不从 Cloneable 和 Serializable 接口继承? 5. 为何 Map 接口不继承 Collection 接口? 6. Iterator 是什么? 7. Enumeration 和 Iterator 接口的区别? ...
java.util.map接口,Java集合框架,hashmap、LinkedHashMap
4)了解Map接口及主要实现类(HashMap、TreeMap、HashTable) 二、实验内容及步骤 1、编写程序练习将以下5个Person类的对象放在一个HashSet中。 姓名:张三 身份证号:178880001 姓名:王五 身份证号:178880002 ...
java集合框架,主要包括sort,list,map接口下的类的详解,希望可以帮助初学者精确地理解其内容
掌握Java集合框架中的三大类集合的特征和适用场合 掌握ArrayList类的使用 掌握HashMap类的使用 了解HashSet类的使用 掌握Collections类的使用 了解集合框架中的其它集合类 集合框架(Collection Framework) java.util...
Java 2集合框架图 集合接口:6个接口(短虚线表示),表示不同集合类型,是集合框架的基础。 抽象类:5个抽象类(长虚线表示),对集合接口的部分实现。可扩展为自定义集合类。 实现类:8个实现类(实线表示),...
集合接口:6个接口,表示不同集合类型,是集合框架的基础。 抽象类:5个抽象类,对集合接口的部分实现。可扩展为自定义集合类。 实现类:8个实现类,对接口的具体实现。 在很大程度上,一旦您理解了接口,您就...