出处:http://www.iteye.com/topic/754887
-
HashMap的数据结构
HashMap主要是用数组来存储数据的,我们都知道它会对key进行哈希运算,哈系运算会有重复的哈希值,对于哈希值的冲突,HashMap采用链表来解决的。在HashMap里有这样的一句属性声明:
transient Entry[] table;
Entry就是HashMap存储数据所用的类,它拥有的属性如下
final K key; V value; final int hash; Entry<K,V> next;
看到next了吗?next就是为了哈希冲突而存在的。比如通过哈希运算,一个新元素应该在数组的第10个位置,但是第10个位置已经有Entry,那么好吧,将新加的元素也放到第10个位置,将第10个位置的原有Entry赋值给当前新加的 Entry的next属性。数组存储的是链表,链表是为了解决哈希冲突的,这一点要注意。
-
几个关键的属性
这个上面已经讲到了
//默认容量 static final int DEFAULT_INITIAL_CAPACITY = 16; //最大容量 static final int MAXIMUM_CAPACITY = 1 << 30; //默认加载因子,加载因子是一个比例,当HashMap的数据大小>=容量*加载因子时,HashMap会将容量扩容 static final float DEFAULT_LOAD_FACTOR = 0.75f; //当实际数据大小超过threshold时,HashMap会将容量扩容,threshold=容量*加载因子 int threshold; //加载因子 final float loadFactor;
-
HashMap的初始过程
构造函数1
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(); }
重点注意这里while (capacity < initialCapacity) capacity <<= 1;
capacity才是初始容量,而不是initialCapacity,这个要特别注意,如果执行new HashMap(9,0.75);那么HashMap的初始容量是16,而不是9,想想为什么吧。
构造函数2public HashMap(int initialCapacity) { this(initialCapacity, DEFAULT_LOAD_FACTOR); }
构造函数3,全部都是默认值public HashMap() { this.loadFactor = DEFAULT_LOAD_FACTOR; threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR); table = new Entry[DEFAULT_INITIAL_CAPACITY]; init(); }
构造函数4public HashMap(Map<? extends K, ? extends V> m) { this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1, DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR); putAllForCreate(m); }
-
如何哈希
HashMap并不是直接将对象的hashcode作为哈希值的,而是要把key的hashcode作一些运算以得到最终的哈希值,并且得到的哈希值也不是在数组中的位置哦,无论是get还是put还是别的方法,计算哈希值都是这一句:
int hash = hash(key.hashCode());
hash函数如下:static int hash(int h) { return useNewHash ? newHash(h) : oldHash(h); }
useNewHash声明如下:private static final boolean useNewHash; static { useNewHash = false; }
这说明useNewHash其实一直为false且不可改变的,hash函数里对 useNewHash的判断真是多余的。private static int oldHash(int h) { h += ~(h << 9); h ^= (h >>> 14); h += (h << 4); h ^= (h >>> 10); return h; } private static int newHash(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); }
其实HashMap的哈希函数会一直都是oldHash。 -
如果确定数据的位置
看下面两行
int hash = hash(k.hashCode()); int i = indexFor(hash, table.length);
第一行,上面讲过了,是得到哈希值,第二行,则是根据哈希指计算元素在数组中的位置了,位置的计算是将哈希值和数组长度按位与运算。static int indexFor(int h, int length) { return h & (length-1); }
“h & (length-1)”其实这里是很有讲究的,为什么是和(length-1)进行按位与运算呢?这样做是为了提高HashMap的效率。什么?这样能提高效率?且听我细细道来。首先我们要确定一下,HashMap的数组长度永远都是偶数,即使你在初始化的时候是这样的new HashMap(15,0.75);因为在构造函数内部,上面也讲过,有这样的一段代码:
while (capacity < initialCapacity) capacity <<= 1;
所以length-1一定是个奇数,假设现在长度为16,减去1后就是15,对应的二进制是:1111。假设有两个元素,一个哈希值是8,二进制是1000,一个哈希值是9,二进制是1001。和1111与运算后,分别还是1000和1001,它们被分配在了数组的不同位置,这样,哈希的分布非常均匀。
那么,如果数组长度是奇数,减去1后就是偶数了,偶数对应的二进制最低位一定是0了,例如14二进制1110。对上面两个数子分别与运算,得到1000和1000。看到了吗?都是一样的值,哈希值8和9的元素多被存储在数组同一个位置的链表中。在操作的时候,链表中的元素越多,效率越低,因为要不停的对链表循环比较。所以,一定要哈希均匀分布,尽量减少哈希冲突,减少了哈希冲突,就减少了链表循环,就提高了效率。
-
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为NULL,则是单独处理的,看看putForNullKey方法:private V putForNullKey(V value) { int hash = hash(NULL_KEY.hashCode()); int i = indexFor(hash, table.length); for (Entry<K,V> e = table[i]; e != null; e = e.next) { if (e.key == NULL_KEY) { V oldValue = e.value; e.value = value; e.recordAccess(this); return oldValue; } } modCount++; addEntry(hash, (K) NULL_KEY, value, i); return null; }
NULL_KEY的声明:static final Object NULL_KEY = new Object();for (Entry<K,V> e = table[i]; e != null; e = e.next) { if (e.key == NULL_KEY) { V oldValue = e.value; e.value = value; e.recordAccess(this); return oldValue; } }
如果遍历完了该位置的链表都没有找到有key相等的,那么将当前对象增加到链表里面去modCount++; addEntry(hash, (K) NULL_KEY, value, i); return null;
且看看addEntry方法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); }
table[bucketIndex] = new Entry<K,V>(hash, key, value, e);新建一个Entry对象,并放在当前位置的Entry链表的头部,看看下面的 Entry构造函数就知道了,注意红色部分。Entry(int h, K k, V v, Entry<K,V> n) { value = v; next = n; key = k; hash = h; }
-
如何扩容?
当put一个元素时,如果达到了容量限制,HashMap就会扩容,新的容量永远是原来的2倍。
上面的put方法里有这样的一段:if (size++ >= threshold) resize(2 * table.length);
这是扩容判断,要注意,并不是数据尺寸达到HashMap的最大容量时才扩容,而是达到 threshold指定的值时就开始扩容, threshold=最大容量*加载因子。 看看resize方法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); }
重点看看红色部分的 transfer方法void transfer(Entry[] newTable) { Entry[] src = table; int newCapacity = newTable.length; for (int j = 0; j < src.length; j++) { Entry<K,V> e = src[j]; if (e != null) { src[j] = null; do { Entry<K,V> next = e.next; int i = indexFor(e.hash, newCapacity); e.next = newTable[i]; newTable[i] = e; e = next; } while (e != null); } } }
tranfer方法将所有的元素重新哈希,因为新的容量变大,所以每个元素的哈希值和位置都是不一样的。 -
如何寻找元素
通 过上面代码的分析,应该可以很清楚的看到,HashMap的元素查找大致分为三步:
根据key的hasocde()得到哈希值
根据哈希值确定元素在数组中的位置
找到指定位置 的链表,循环比较,先“==”比较,如果不等,再“equals”比较,如果有一个比较相等,就说明找到元素了。
所以说到这里,我想大家也明白了,为什么要把一个对象放进HashMap的时候,最好是重写hashcode()方法和equals 方法呢?根据前面的分析,hashcode()可以确定元素在数组中的位置,而equals方法在链表的比较时要用到。
-
正确的使用HashMap
1:不要在并发场景中使用HashMap
HashMap是线程不安全的,如果被多个线程共享的操作,将会引发不可预知的问题,据sun的说法,在扩容时,会引起链表的闭环,在get元素时,就会无限循环,后果 是cpu100%。
看看get方法的红色部分
public V get(Object key) {
if (key == null) return getForNullKey(); int hash = hash(key.hashCode()); for (Entry<K,V> e = table[indexFor(hash, table.length)]; e != null; e = e.next) { Object k; if (e.hash == hash && ((k = e.key) == key || key.equals(k))) return e.value; } return null; }
2:如果数据大小是固定的,那么最好给HashMap设定一个合理的容量值
根据上面的分析,HashMap的初始默认容量是16,默认加载因子是0.75,也就是说,如果采用HashMap的默认构造函数,当增加数据时,数据实际容量超过10*0.75=12 时,HashMap就扩容,扩容带来一系列的运算,新建一个是原来容量2倍的数组,对原有元素全部重新哈希,如果你的数据有几千几万个,而用默认的HashMap构造函 数,那结果是非常悲剧的,因为HashMap不断扩容,不断哈希,在使用HashMap的场景里,不会是多个线程共享一个HashMap,除非对HashMap包装并同步,由此产生的内 存开销和cpu开销在某些情况下可能是致命的。
2011-02-24 david.wang
发表评论
-
JVM内存模型及垃圾收集策略解析
2011-09-25 01:56 863一 JVM内存模型 1.1 Java栈 Java栈 ... -
JVM基础概念总结:数据类型、堆与栈
2011-09-25 01:14 851数据类型 Java虚拟机中,数据类型可以分为两类:基本类型 ... -
JVM分代垃圾回收策略的基础概念
2011-09-25 01:07 720为什么要分代 分代的垃圾回收策略,是基于这样一个事实:不 ... -
理解静态变量惰性初始化的双检锁模式
2011-05-10 22:28 1217对于双检锁,其实有多种不同的用法,有很多种用法是无论 ... -
基本类型 加减运算 类型转换问题讨论
2011-03-09 14:56 972先来看下面的 代码: public class Tes ... -
DataSource 使用方法
2011-03-03 14:26 3026转自:http://marshal.easymorse.com ... -
Java util之常用数据类型特性盘点(Map 四种同步方式的性能比较)
2011-02-24 20:09 1882出处:http://www.iteye.com/topic/1 ... -
Java util之常用数据类型特性盘点 (三)
2011-02-24 16:22 1091Java util之常用数据类型特性盘点 (三) 出处 ... -
Java util之常用数据类型特性盘点 (二)
2011-02-24 16:07 1066Java util之常用数据类型特性盘点 (二) 出处 ... -
Java util之常用数据类型特性盘点(一)
2011-02-24 15:47 1000Java util之常用数据类型特性盘点 出处:http:// ... -
Java 中实例化对象方法
2011-02-24 13:57 10611、直接 new 调用默认构造器实例化对象,如: ... -
java 冒泡排序、选择排序、插入排序、快速排序二分法查找代码
2011-02-23 20:42 4075java 排序的代码 import java.util ... -
java collection集合框架
2011-02-23 17:19 1387Java集合框架使用总 ... -
java.sql.Date与java.util.Date 异同
2011-02-23 17:13 1333java.util.Date 包含日期和时间。 ... -
类的初始化顺序问题
2011-02-23 16:10 736一道面试题目,看代码: public class ... -
java clone方法使用详解
2011-02-23 15:39 909java clone方法使用 出处 ... -
Java数据类型
2011-02-23 15:04 709Java数据类型 JAVA语言中定义了8种基本的数据类型, ... -
java float double为什么精度会丢失
2011-02-23 14:39 5757由于对float或double 的使用不当,可能会出现精度丢失 ... -
java基础知识回顾(1)float/double 与封装类型Float/Double
2011-02-23 14:31 3547float/double 与封装类型Float/Double ... -
HashSet \LinkedHashSet\TreeSet 元素顺序
2011-02-23 13:36 1288import java.util.Arrays; im ...
相关推荐
以下是一些Java中常用的Util类及其重要知识点的详细说明: 1. **ArrayList和LinkedList**: 这两个都是`java.util`包下的List接口实现类。ArrayList基于动态数组,适合随机访问,插入和删除操作相对较慢;LinkedList...
java util工具类2java util工具类2java util工具类2java util工具类2
在阅读博客文章(链接已给出,但无法访问)时,可能涉及了更多关于Java Util的深入分析或源码解读,如类的实现原理、性能优化等。对于`util2`和`util`这两个文件,可能是示例代码或者自定义的工具类库,它们可以...
Java的`util`工具类是Java标准库中的核心部分,为开发者提供了丰富的功能,极大地简化了编程工作。这个包包含了各种集合框架、日期时间处理、随机数生成、字符串操作、IO流处理等实用工具类。在Java编程中,熟练掌握...
在Java中,`java.util` 包是最基础也是最常用的工具类集合,而"Java常用Util类Jar"则是一个包含了更多自定义或者网络上流行实用工具类的集合,适用于Web项目的快速开发。 这个压缩包中的`ZycUtil`可能是一个自定义...
Mysql、Oracle 中的数据类型与 Java 中的数据类型对应表 MySQL 和 Oracle 是两种常用的关系型数据库管理系统,而 Java 是一种广泛应用于企业级应用开发的编程语言。在数据库应用开发中,理解数据类型的对应关系...
在Java编程中,工具类(Util Class)是包含各种实用函数的静态类,它们提供了一种简化常见任务的方法。在给定的`UtilClass`中,我们有五个主要的工具类:`StringUtil`、`FileUtil`、`ConnectDB`、`DateUtil`和`...
java util工具类4java util工具类4java util工具类4java util工具类4ssss
这个包下有很多重要的类,如ArrayList、HashMap、LinkedList、Date、Calendar等,它们提供了许多常用的功能,使得开发者在处理数据结构、集合操作、时间日期等方面的工作变得更加便捷。下面将详细介绍一些`util`包中...
Java中的`util`工具类是Java Standard Edition (Java SE)库中的重要组成部分,它们提供了许多实用功能,极大地简化了开发工作。在这个主题中,我们将深入探讨`StringUtil`、`FileUtil`、`MD5`、`JsonUtil`以及`...
### 使用 Java.util.zip 包实现数据压缩与解压 在计算机科学领域,数据压缩技术是一项重要的功能,它能够帮助减少存储空间的需求以及提高网络传输效率。本文将通过一系列的示例来详细介绍如何利用 Java 中的 `java....
Java.util包是Java标准库中的核心包之一,它包含了大量用于通用编程的类和接口,是Java开发中不可或缺的一部分。这个包提供了数据结构、集合框架、事件处理、日期时间、随机数生成、位集以及与I/O流操作相关的辅助...
Java工具类(Java Util)是Java开发中不可或缺的一部分,它为开发者提供了大量便捷的功能,极大地提高了开发效率。在Java标准库中,`java.util`包是核心工具类库,包含了各种容器类、集合框架、日期时间处理、随机数...
在Java中,`java.util`包提供了多种数据结构的实现,包括线性表、链表和哈希表。以下是对这些数据结构及其在Java中的具体实现的详细分析: 1. **线性表**: - **ArrayList**: 作为线性表的一种实现,ArrayList是一...
java自己封装的工具类,用于节省时间,提高效率,java常用工具类封装util.rar 一个项目不可能没有工具类,工具类的初衷是良好的,代码重用,但到了后面工具类越来越乱,有些项目工具类有几十个,看的眼花缭乱,...
在学习过程中,可以通过编写小型项目来实践,例如创建一个文件浏览器,使用Swing展示目录结构,用户选择文件后,使用IO读取文件内容,并利用Util进行简单的数据分析。这样既能巩固理论知识,也能提升实际编程技能。
Java util是Java编程语言中的一个核心包,包含了各种通用的工具类,对于任何Java开发者来说,理解和掌握这个包中的类和方法都是非常基础且重要的。在Java的util包中,我们可以找到许多用于处理集合、日期时间、...
java.util是Java的标准库中的一个包,主要用于数据结构、日期和时间处理等。 在java.util包中,包含了一些Java集合框架的基础类,比如Enumeration、Hashtable、Stack、Vector等,以及日期和时间处理相关的类,如...
import java.util.HashMap; public class HelloMap { public HashMap, String> setMap(HashMap, String> map) { return map; } public HashMap, String> getMap(HashMap, String> map) { return setMap(map);...