java.util.HashMap深度学习
一、散列表初探：
同一问题可用不同算法解决，而一个算法的质量优劣将影响到算法乃至程序的效率。算法分析的目的在于选择合适算法和改进算法。一个算法的评价主要从时间复杂度和空间复杂度来考虑。
时间复杂度是指执行算法所需要的计算工作量；而空间复杂度是指执行这个算法所需要的内存空间。两者均体现在消耗计算机重要的两个资源方面。
数据结构中有数组和链表来实现对数据的存储，但这两者基本上是两个极端，数组存储区间是连续的，占用内存严重，故空间复杂的很大。但数组的二分查找时间复杂度小，为O(log2N)；而链表存储区间离散，占用内存比较宽松，故空间复杂度很小，但时间复杂度很大，达O（N）。显然，现实生活中的数据并不会走在这两个极端，更多的是追求空间和时间的均衡。而哈希表（(Hash table）的提出既满足了数据的查找方便，同时不占用太多的内容空间，使用也十分方便。
打个比方来说，所有的数据就好像许许多多的书本。如果这些书本是一本一本堆起来的，就好像链表或一样，整个数据会显得非常的无序和凌乱，在你找到自己需要的书之前，你要经历许多的查询过程；而如果你对所有的书本进行编号，并且把这些书本按次序进行排列的话，那么如果你要寻找的书本编号是n，那么经过二分查找，你很快就会找到自己需要的书本。但是如果你每一个种类的书本都不是很多，那么你就可以对这些书本进行归类，哪些是文学类，哪些是艺术类，哪些是工科的，哪些是理科的，你只要对这些书本进行简单的归类，那么寻找一本书也会变得非常简单，比如说如果你要找的书是计算机方面的书，那么你就会到工科一类当中去寻找，这样查找起来就会显得比较简单。
既然哈希表（(Hash table）如此神通广大，那不得不揭开她的神秘面纱啦。
哈希表主要分为几个部分和功能：
散列（hash）：散列函数：将数据的hashCode映射到散列表中的位置，此过程不需给出冲突解决方案。
好的散列函数的2个必备条件：1，快捷，在O（1）时间内运行；2，均匀的分布hashCode，填充概率相同。
冲突解决方案（collision solution）：当一个新项散列到已经被占据的散列表中的位置时，被告之发生冲突，解决方案用于确定新项可以插入散列表中未被占据的位置。
解决冲突主要的主要方法：开放寻址方法（寻找另外的空位）；封闭寻址方法（吊挂另一种数据结构）
一般采用后者挂链表的方式。
再散列（rehash）：当数据的容量大于散列表的容量的容量时，那么创建一张指定新容量的表，再将原来表中的数据映射到新表中。
二、java.util.HashMap的源码解析
java.util.HashMap是很常见的类，实现了java.util.Map<K,V>接口
HashMap主要是用数组来存储数据的，我们都知道它会对key进行哈希运算，
哈系运算会有重复的哈希值，对于哈希值的冲突，HashMap采用链表（挂链）来解决的。
HashMap结构如下图
HashMap属性
在HashMap里的属性声明：
transient Entry<K,V>[] table;//HashMap链表数组，数组的每一项存储一个链表
transient int size;//大小，2的幂，默认16
int threshold;//阈值上限 = 容量 * 负载因子
final float loadFactor;//负载因子，默认0.75
项的存储
Entry就是HashMap存储数据所用的类，相当于链表的节点。它拥有的属性如下
static class Entry<K,V> implements Map.Entry<K,V> {
final K key;
V value;
Entry<K,V> next;
int hash;
}
看到next了吗？next就是为了哈希冲突而存在的。比如通过哈希运算，一个新元素应该在数组的第10个位置，但是第10个位置已经有Entry，那么好吧，将新加的元素也放到第10个位置，将第10个位置的原有Entry赋值给当前新加的 Entry的next属性。数组存储的是链表，链表是为了解决哈希冲突的。
添加项
HashMap的方法put是把一个<key,value>对添加到哈希表中
Java JDK中的源码：
public V put(K key, V value) {
if (key == null)
return putForNullKey(value);
int hash = hash(key);
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，则将hashCode映射到table[0]中。
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;
}
第二条语句是散列函数hash，这个暂时放在后面分析。
第三条语句是得到hashCode之后将HashCode映射到表中的位置。
/**
* Returns index for hash code h.
*/
static int indexFor(int h, int length) {
return h & (length-1);
}
方法里面使用了按位取并&的操作符。例如h=25,length=16,把那么返回值就为9。
作用上相当于取模mod或者取余%，但是因为按位取并&不涉及除法，直接进入CPU运算，故能更快的得到结果、（前提为length是2的幂）
第四条语句是循环遍历表中的数据，检查传入的关键字key是否已经存在，假如已经存在，那么用传入的新值取代原关键字关联的值，并返回旧值。
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
关于判断条件if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
首先，key的hash code必须和映射位置的hash code相同，否则，无需进行下一步判断。
如果传入的值和旧值都为null，则使用==判断，否则使用equals检测。
第五条语句主要是addEntry方法（其他略过），将数据添加到链表中指定的节点位置
void addEntry(int hash, K key, V value, int bucketIndex) {
if ((size >= threshold) && (null != table[bucketIndex])) {
resize(2 * table.length);
hash = (null != key) ? hash(key) : 0;
bucketIndex = indexFor(hash, table.length);
}
createEntry(hash, key, value, bucketIndex);
}
void createEntry(int hash, K key, V value, int bucketIndex) {
Entry<K,V> e = table[bucketIndex];
table[bucketIndex] = new Entry<>(hash, key, value, e);
size++;
}
resize(2 * table.length)是再散列过程，扩大为原来的2倍保证了是2的幂，后面介绍。
散列函数hash
通过hash方法的到key对象的哈希码。具体如下：
final int hash(Object k) {
int h = 0;
if (useAltHashing) {
if (k instanceof String) {//备用的hash函数，容量超过Integer.MAX_VALUE使用
return sun.misc.Hashing.stringHash32((String) k);
}
h = hashSeed;
}
h ^= k.hashCode();
//加入高位计算，解决在低位不变，高位变化情况下引起hash冲突严重问题
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
通过上述代码我们可以很深刻的理解到，通过key值的hashCode方法返回的hash码，来产生索引i。如果table[i]为null，则此处没有键值对，可以直接插入。如果table[i]！=null则此处有元素则上面的for循环就是存储的新的Entry元素。
再散列rehash过程
当哈希表的容量超过默认容量时，必须调整table的大小。当容量已经达到最大可能值时，那么该方法就将容量调整到Integer.MAX_VALUE返回，这时，需要创建一张新表，将原表的映射到新表中。
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];
boolean oldAltHashing = useAltHashing;
useAltHashing |= sun.misc.VM.isBooted() &&
(newCapacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
boolean rehash = oldAltHashing ^ useAltHashing;
transfer(newTable, rehash);
table = newTable;
threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}
/**
* Transfers all entries from current table to newTable.
*/
void transfer(Entry[] newTable, boolean rehash) {
int newCapacity = newTable.length;
for (Entry<K,V> e : table) {
while(null != e) {
Entry<K,V> next = e.next;
if (rehash) {
e.hash = null == e.key ? 0 : hash(e.key);
}
int i = indexFor(e.hash, newCapacity);
e.next = newTable[i];
newTable[i] = e;
e = next;
}
}
}
tranfer方法将所有的元素重新哈希，由于新表的规模变大，所以映射到表中的位置就将变化，重新按位取并就得到新的位置。但在此过程由于关键字key关联的<K,V>键值对一桶存储它的hash Code，可以避免重复计算散列所需要的hash code。
搜索操作
搜索操作通过get方法来实现，并返回<k,v>键值对中的V。
public V get(Object key) {
if (key == null)
return getForNullKey();
Entry<K,V> entry = getEntry(key);
return null == entry ? null : entry.getValue();
}
**
* Returns the entry associated with the specified key in the
* HashMap. Returns null if the HashMap contains no mapping
* for the key.
*/
final Entry<K,V> getEntry(Object key) {
int hash = (key == null) ? 0 : hash(key);
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 != null && key.equals(k))))
return e;
}
return null;
}
正确的使用HashMap：不要在并发场景中使用HashMap
HashMap是线程不安全的，如果被多个线程共享的操作，将会引发不可预知的问题。
扩容时，会引起链表的闭环，在get元素时（红色标记），就会无限循环，后果是cpu100%。
Hashtable简要分析
如上，HashMap线程不是安全的，而Hashtable使用线程同步，每一种方法都有synchronized关键字。这是与HashMap主要不同的一点。
同作为一种哈希表，不同的地方还体现在一下几个方面。
继承关系不同：Hashtable继承自Dictionary，而HashMap继承自AbstractMap，同实现Map接口。
public class Hashtable<K,V> extends Dictionary<K,V> implements Map<K,V>, Cloneable, java.io.Serializable
public class HashMap<K,V> extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable
默认容量为11，扩容容量为原来的2倍+1；而不是HashMap那样满足2的指数幂。
newCapacity = (oldCapacity << 1) + 1;
映射函数不同：
int index = (hash & 0x7FFFFFFF) % tab.length;
不能传入空的key或者value：
if (value == null) {
throw new NullPointerException();
}
这样看来，Hashtable的确比HashMap历史要悠久...
自定义HashMap的实现。
在此就不贴代码了，其余的与系统设计的代码大同小异。主要修改了系统提供的hash函数
/**
* 哈希函数
*
* @param k
* @return
*/
private int hash(String k) {
int hash = 0;
hash ^= k.hashCode();
//将各个位置的字符对应的ASCII码相加
for (int i = 0; i < k.length(); ++i) {
hash += k.charAt(i);
}
//位运算，增加碰撞的几率
hash += (hash << 3);
hash ^= (hash >>> 7);
hash += (hash << 15);
return hash;
}
下面来测试一把，主要在哈希表新建项，下面是往表里面插入1000000项的测试结果
package com.HashMap20131029;
/**
* 自定义哈希表与系统哈希表测试类
* @author YangKang
*
*/
public class MapTest {
/**
* 主函数
*
* @param args
*/
public static void main(String[] args) {
long startTime = System.currentTimeMillis();
java.util.HashMap<String,String> hm = new java.util.HashMap<String,String>();
for (int i = 0; i < 1000000; i++) {
hm.put("key" + i, "value" + i);
}
long endTime = System.currentTimeMillis();
System.out.println("系统提供的hashmap所花时间：" + (endTime - startTime));
long startTime2 = System.currentTimeMillis();
MyHashMap myhm = new MyHashMap();
for (int i = 0; i < 1000000; i++) {
myhm.put("key" + i, "value" + i);
}
long endTime2 = System.currentTimeMillis();
System.out.println("自定义hashmap所花时间：" + (endTime2 - startTime2));
}
}
/** log output
*系统提供的hashmap所花时间：2384
*自定义hashmap所花时间：1378
*/
其实测试添加100项的时候，java sdk提供的HashMap还是占明显优势的。
这告诉我们成功是有先决条件的
源代码打包已经上传：http://pan.baidu.com/share/link?shareid=2333258039&uk=219034104
希望大家多多支持和指正。
相关推荐
07丨深入浅出HashMap的设计与优化.html
《深入浅出Java》这本书以其独特的讲解方式，旨在让学习者轻松掌握复杂的Java编程语言。"深入浅出"这一理念，意味着作者通过直观、生动的示例和丰富的图解，帮助读者逐步理解Java的核心概念和技术。 Java是一种广泛...
开篇词讲怎样才能做好性能调优02讲如何制定性能调优策略04讲慎重使用正则表达式05讲ArrayList还是LinkedList使用不当性能差千倍07讲深入浅出HashMap的设计与优化08讲网络通信优化之IO模型：如何解决高并发下IO瓶颈09...
《深入浅出Java语言程序设计》是一本专为Java初学者和进阶者精心编写的教程，旨在帮助读者全面理解并掌握Java编程的核心概念和技术。本书涵盖了从基础语法到高级特性的广泛内容，旨在使读者能够熟练运用Java进行软件...
在深入浅出的讲解中，本书涵盖了Java编程的基础知识，包括： 1. **Java简介**：首先介绍Java的历史背景、特点以及为什么选择Java作为学习的编程语言。书中可能以生动的故事或比喻解释，帮助读者理解Java在软件开发...
【标题】"Java深入浅出哥哥复合管"可能是指一个关于Java编程的教程或课程，其中"哥哥复合管"可能是作者或讲师的别称，或者是某种特定编程概念的比喻。这个标题暗示了内容将深入讲解Java语言，并可能涵盖一些高级或...
《深入浅出Java 2面向对象程序设计》是一本针对Java编程初学者和进阶者的重要教程，旨在帮助读者深入理解和掌握面向对象编程的核心概念和技术。面向对象编程（Object-Oriented Programming，简称OOP）是Java语言的...
《深入浅出Java2面向对象程序设计》是一本旨在帮助读者深入理解Java编程语言和面向对象编程概念的书籍。随书附带的光盘包含了源代码、习题解答以及实验工具，为学习者提供了丰富的实践资源，使得理论与实践相结合，...
《深入浅出Java语言程序设计》是一本专为初学者和有一定基础的程序员设计的教程，旨在通过由浅入深的方式，系统性地讲解Java编程的核心概念和技术。这本书的特色在于其详细的解释和通俗易懂的语言，使得学习者能够...
《深入浅出Java语言程序设计》是一本旨在帮助初学者和有一定经验的开发者更深入理解Java编程的教材。这本书不仅覆盖了Java的基础知识，还深入探讨了许多高级特性，帮助读者构建坚实的Java编程基础。 首先，Java的...
《Java2深入浅出》是一本旨在帮助读者全面掌握Java编程技术的教材，结合源码进行讲解，适合从初学者到有一定经验的开发者阅读。这本书分为入门、进阶和应用实例三个部分，由人民邮电出版社出版，为学习Java语言提供...
《深入浅出Java2源代码》是一本专为Java初学者和进阶者设计的教材，旨在通过深入解析Java2的源代码，帮助读者更好地理解并掌握这门强大的编程语言。光盘中包含的源代码是书中实例和讲解的重要组成部分，它们提供了...
本精讲将深入浅出地探讨Java的基础知识，旨在为初学者提供一个全面且易理解的学习路径。 1. **Java简介**：Java是由Sun Microsystems（现为Oracle Corporation）于1995年发布的，它的设计目标是“一次编写，到处...
《深入浅出Java语言程序设计》是一本专为学习和理解Java编程语言而编写的教材。这本书的内容丰富，涵盖了从基础语法到高级特性的全面解析，旨在帮助读者深入理解Java编程的核心概念和技术。 首先，Java作为一门面向...
《深入浅出Java语言程序设计》是一本专为学习和理解Java编程语言而设计的教材。这本书涵盖了从基础到高级的Java编程概念，旨在帮助读者深入理解Java的各个方面，从而能够熟练地进行软件开发。 首先，Java语言是面向...