文章目录
一：HashMap1、HashMap的简介2、resize()扩容3、哈希冲突4、HashMap的常用操作5、HashMap源码分析6、MyHashMap
二：HashTable1、HashTable的简介2、HashTable的特点（1）HashTable的继承关系（2）HashTable的存储结构（3）HashTable的遍历方式
3、HashTable源码分析4、HashTable的常用操作
三：HashMap和HashTable的区别
一：HashMap
1、HashMap的简介
HashMap 继承于AbstractMap，实现了Map、Cloneable、java.io.Serializable接口。哈希表是一个散列表（即数组和链表的结合体），其存储的内容是一个键值对（key-value）HashMap中的key-value都是存储在Entry中的，针对任意的key通过哈希算法 转换为固定的位置（数组），HashMap的底层结构是一个数组，数组中的每一项是一条链表。HashMap可以存null键和null值，不保证元素的顺序恒久不变，他的底层使用的是数组和链表，通过hashCode()方法和equals方法保证键的唯一性。HashMap 的实例有两个参数影响其性能：“初始容量” 和 “加载因子”。容量 是哈希表中桶的数量，初始容量 只是哈希表在创建时的容量。加载因子 是哈希表在其容量自动增加之前可以达到多满的一种尺度。当哈希表中的条目数超出了加载因子与当前容量的乘积时，则要对该哈希表进行 rehash 操作（即重建内部数据结构），从而哈希表将具有大约两倍的桶数。通常，默认加载因子是0.75。 节点个数大于8时，采用数组+链表+红黑树结构；节点个数小于6时，采用数组+链表
2、resize()扩容
3、哈希冲突
哈表冲突通常以下几种方式构造哈希函数1）直接定址法 key address(key) = a*key + b2）平方取中法 key 108 109 110 = 108^2 109^2 110^23）折叠法 key -》 拆分为几部分 区域号-书架号-图书编号4）除留取余法 key -》 hash表的最大长度m 取不大于m的质数 key%质数
解决冲突1）开放地址法 12 13 25 23 hash表的长度14 hash函数key%132）链地址法
4、HashMap的常用操作
public class HashMapTest {
public static void main(String
[] args
) {
HashMap
<String, Integer> map
= new HashMap<>();
map
.put("Tom", 12);
map
.put("Jack", 15);
map
.put("Jim", 20);
map
.put("Tom", 65);
map
.put(null
, 100);
map
.remove("Jack");
map
.replace("Jim", 200);
System
.out
.println("遍历方法一：使用迭代器正向遍历key值和value值");
Iterator
<Map
.Entry
<String, Integer>> iterator
= map
.entrySet().iterator();
while (iterator
.hasNext()) {
Map
.Entry
<String, Integer> next
= iterator
.next();
System
.out
.println("key值：" + next
.getKey() + " value值：" + next
.getValue());
}
System
.out
.println("===========================================================");
System
.out
.println("遍历方法二：使用foreach方法遍历key值和value值");
for (Map
.Entry
<String, Integer> next
: map
.entrySet()) {
System
.out
.println("key值：" + next
.getKey() + " value值：" + next
.getValue());
}
System
.out
.println("===========================================================");
System
.out
.println("使用迭代器单一遍历key值");
Iterator
<String> iterator_key
= map
.keySet().iterator();
while (iterator_key
.hasNext()) {
String key
= iterator_key
.next();
System
.out
.println("key值：" + key
);
}
System
.out
.println("===========================================================");
System
.out
.println("使用迭代器单一遍历value值");
Iterator
<Integer> iterator_value
= map
.values().iterator();
while (iterator_value
.hasNext()) {
Integer value
= iterator_value
.next();
System
.out
.println("value值：" + value
);
}
System
.out
.println("===========================================================");
System
.out
.println("使用foreach方法单一遍历key值");
for (String key
: map
.keySet()) {
System
.out
.println("key值：" + key
);
}
System
.out
.println("===========================================================");
System
.out
.println("使用foreach方法单一遍历value值");
for (Integer value
: map
.values()) {
System
.out
.println("value值：" + value
);
}
}
}
运行结果
5、HashMap源码分析
主要成员变量
transient int size
;
int threshold
;
final float loadFactor
;
transient int modCount
;
构造函数 当采用无参构造时，HashMap会先将table数组赋值为空数组，待第一次添加元素时，会使用默认构造值：initialCapacity默认为16，loadFactory默认为0.75。
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
);
this.loadFactor
= loadFactor
;
threshold
= initialCapacity
;
init();
}
添加函数
public V
put(K key
, V value
) {
if (table
== EMPTY_TABLE
) {
inflateTable(threshold
);
}
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
;
}
inflateTable这个方法用于为主干数组table在内存中分配存储空间，通过roundUpToPowerOf2(toSize)可以确保capacity为大于或等于toSize的最接近toSize的二次幂，比如toSize=13,则capacity=16；to_size=16，capacity=16；to_size=17，capacity=32。
private void inflateTable(int toSize
) {
int capacity
= roundUpToPowerOf2(toSize
);
threshold
= (int) Math
.min(capacity
* loadFactor
, MAXIMUM_CAPACITY
+ 1);
table
= new Entry[capacity
];
initHashSeedAsNeeded(capacity
);
}
roundUpToPowerOf2中的这段处理使得数组长度一定为2的次幂，Integer.highestOneBit是用来获取最左边的bit（其他bit位为0）所代表的数值
private static int roundUpToPowerOf2(int number
) {
return number
>= MAXIMUM_CAPACITY
? MAXIMUM_CAPACITY
: (number
> 1) ? Integer
.highestOneBit((number
- 1) << 1) : 1;
}
Hash函数
final int hash(Object k
) {
int h
= hashSeed
;
if (0 != h
&& k
instanceof String) {
return sun
.misc
.Hashing
.stringHash32((String
) k
);
}
h
^= k
.hashCode();
h
^= (h
>>> 20) ^ (h
>>> 12);
return h
^ (h
>>> 7) ^ (h
>>> 4);
}
以上hash函数计算出的值，通过indexFor进一步处理来获取实际的存储位置。
static int indexFor(int h
, int length
) {
return h
& (length
-1);
}
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
);
}
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
, initHashSeedAsNeeded(newCapacity
));
table
= newTable
;
threshold
= (int)Math
.min(newCapacity
* loadFactor
, MAXIMUM_CAPACITY
+ 1);
}
而至于HashMap为何使用2倍扩容： 我们可以看到上面的indexFor()方法是将通过key值获取到的hash值转化为可以存储的下标值index，而其所使用的方法为return h & (length-1);其实针对转化hash值为index值的方法还有一种十分简单的：return h % length;这两种方法在处理的数值length为2的幂次方时所得到的结果是相同的，但是按位运算的效率要大于普通的算数运算，这也是为什么HashMap采用第一种方法的原因。因此我们也同样可以看出为什么HashMap的初始容量为16；以及为什么HashMap的扩容方法为2倍扩容。目的就是为了保证数组大小始终为2的幂次方，从而保证使用位运算计算index值时的正确性。当我们传入指定参数进行构造table的大小时，HashMap会调用private static int roundUpToPowerOf2(int number)方法来确保参数大小始终为2的幂次方。
transfer
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
;
}
}
}
get方法
public V
get(Object key
) {
if (key
== null
)
return getForNullKey();
Entry
<K,V> entry
= getEntry(key
);
return null
== entry
? null
: entry
.getValue();
}
getEntry
final Entry
<K,V> getEntry(Object key
) {
if (size
== 0) {
return null
;
}
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
;
}
删除
public V
remove(Object key
) {
Entry
<K,V> e
= removeEntryForKey(key
);
return (e
== null
? null
: e
.value
);
}
final Entry
<K,V> removeEntryForKey(Object key
) {
if (size
== 0) {
return null
;
}
int hash
= (key
== null
) ? 0 : hash(key
);
int i
= indexFor(hash
, table
.length
);
Entry
<K,V> prev
= table
[i
];
Entry
<K,V> e
= prev
;
while (e
!= null
) {
Entry
<K,V> next
= e
.next
;
Object k
;
if (e
.hash
== hash
&&
((k
= e
.key
) == key
|| (key
!= null
&& key
.equals(k
)))) {
modCount
++;
size
--;
if (prev
== e
)
table
[i
] = next
;
else
prev
.next
= next
;
e
.recordRemoval(this);
return e
;
}
prev
= e
;
e
= next
;
}
return e
;
}
6、MyHashMap
class MyHashMap<K,V>{
private Node
<K, V>[] table
;
private int size
;
class Node<K,V>{
protected K key
;
protected V value
;
protected int hash
;
protected Node
<K, V> next
;
public Node(K key
, V value
, int hash
) {
this.key
= key
;
this.value
= value
;
this.hash
= hash
;
}
}
public MyHashMap(int capacity
){
table
= new Node[capacity
];
}
public Iterator
<Node
<K, V>> iterator(){
return new Itr();
}
class Itr implements Iterator<Node
<K, V>>{
private int currentIndex
;
private Node
<K, V> nextNode
;
private Node
<K, V> currentNode
;
public Itr(){
if(MyHashMap
.this.isEmpty()){
return;
}
for(int i
=0; i
< table
.length
; i
++){
currentIndex
= i
;
Node
<K, V> firstNode
= table
[i
];
if(firstNode
!= null
){
nextNode
= firstNode
;
return;
}
}
}
@Override
public boolean hasNext() {
return nextNode
!= null
;
}
@Override
public Node
<K, V> next() {
currentNode
= nextNode
;
nextNode
= nextNode
.next
;
if(nextNode
== null
){
for(int i
=currentIndex
+1; i
<MyHashMap
.this.table
.length
; i
++){
currentIndex
= i
;
Node
<K,V> firstNode
= MyHashMap
.this.table
[currentIndex
];
if(firstNode
!= null
){
nextNode
= firstNode
;
break;
}
}
}
return currentNode
;
}
@Override
public void remove() {
if(currentNode
== null
){
return;
}
K currentKey
= currentNode
.key
;
MyHashMap
.this.remove(currentKey
);
currentNode
= null
;
}
}
public void resize(){
Node
<K, V>[] newTable
= new Node[table
.length
* 2];
for(int i
=0; i
<table
.length
; i
++){
rehash(i
, newTable
);
}
this.table
= newTable
;
}
public void rehash(int index
, Node
<K,V>[] newTable
){
Node
<K, V> currentNode
= table
[index
];
if(currentNode
== null
){
return;
}
Node
<K, V> lowListHead
= null
;
Node
<K, V> lowListTail
= null
;
Node
<K, V> highListHead
= null
;
Node
<K, V> highListTail
= null
;
while(currentNode
!= null
){
int newIndex
= newTable
.length
-1 & hash(currentNode
.key
);
if(newIndex
== index
){
if(lowListHead
== null
){
lowListHead
= currentNode
;
lowListTail
= currentNode
;
}else{
lowListTail
.next
= currentNode
;
lowListTail
= lowListTail
.next
;
}
}else{
if(highListHead
== null
){
highListHead
= currentNode
;
highListTail
= currentNode
;
}else{
highListTail
.next
= currentNode
;
highListTail
= lowListTail
.next
;
}
}
currentNode
= currentNode
.next
;
}
if(lowListTail
!= null
){
newTable
[index
] = lowListHead
;
lowListHead
.next
= null
;
}
if(highListTail
!= null
){
newTable
[index
+this.table
.length
] = highListHead
;
highListHead
.next
= null
;
}
}
public int hash(Object key
) {
int h
;
return (h
= key
.hashCode()) ^ (h
>>> 16);
}
public void put(K key
, V value
){
int hash
= hash(key
);
int index
= table
.length
-1 & hash
;
Node
<K, V> firstNode
= table
[index
];
if(firstNode
== null
){
table
[index
] = new Node(key
, value
, hash
);
size
++;
}else{
if(firstNode
.key
.equals(key
)){
firstNode
.value
= value
;
}else{
Node
<K,V> tmp
= firstNode
;
while(tmp
.next
!= null
&& !tmp
.key
.equals(key
)){
tmp
= tmp
.next
;
}
if(tmp
.next
== null
){
if(tmp
.key
.equals(key
)){
tmp
.value
= value
;
}else{
tmp
.next
= new Node(key
, value
, hash
);
size
++;
}
}else{
tmp
.value
= value
;
}
}
}
}
public boolean remove(K key
){
int hash
= hash(key
);
int index
= table
.length
-1 & hash
;
Node
<K, V> firstNode
= table
[index
];
if(firstNode
== null
){
return false;
}else{
if(firstNode
.next
== null
){
if(firstNode
.key
.equals(key
) && firstNode
.hash
== hash
){
table
[index
] = null
;
return true;
}
}
Node
<K,V> tmpPrev
= firstNode
;
Node
<K, V> tmp
= firstNode
.next
;
while(tmp
.next
!= null
){
if(tmp
.key
.equals(key
) && tmp
.hash
== hash
){
tmpPrev
.next
= tmp
.next
;
size
--;
}else{
tmpPrev
= tmp
;
tmp
= tmp
.next
;
}
}
}
return false;
}
public Node
<K,V> get(K key
){
int hash
= hash(key
);
int index
= table
.length
- 1 & hash
;
Node
<K, V> firstNode
= table
[index
];
if (firstNode
== null
) {
return null
;
}
if (hash
== firstNode
.hash
&& key
== firstNode
.key
) {
return firstNode
;
} else {
Node
<K, V> currentNode
= firstNode
.next
;
while (currentNode
!= null
) {
if (currentNode
.hash
== hash
&& currentNode
.key
== key
) {
return currentNode
;
}
currentNode
= currentNode
.next
;
}
}
return null
;
}
public boolean isEmpty(){
return size
== 0;
}
}
二：HashTable
1、HashTable的简介
HashTable同样是基于哈希表实现的，其中的每个元素是一个key-value对，内部也是通过单链表解决冲突问题，容量不足（超过了阀值）时，同样会自动增长。它在很大程度上和HashMap的实现差不多，不过相对的功能较少，目前已经很少使用了，下面来看看HashTable的具体内容。
2、HashTable的特点
（1）HashTable的继承关系
public class Hashtable<K,V>
extends Dictionary<K,V>
implements Map<K,V>, Cloneable
, java
.io
.Serializable
{
}
从中可以看出HashTable继承Dictionary类，实现Map接口。其中Dictionary类是任何可将键映射到相应值的类（如 Hashtable）的抽象父类。每个键和每个值都是一个对象。在任何一个 Dictionary 对象中，每个键至多与一个值相关联。
实现了Map接口，是"key-value键值对"接口。即接口中的每个元素都是一对， 以key-value的形式保存，并且Key是不重复的，元素的存储位置由key决定。也就是可以通过key去寻找key-value的位置，从而得到value的值。适合做查找工作。实现了Cloneable接口，能被克隆。Cloneable是标记型的接口，它们内部都没有方法和属性，实现 Cloneable来表示该对象能被克隆，能使用Object.clone()方法。如果没有实现 Cloneable的类对象调用clone()就会抛出CloneNotSupportedException。实现了Serializable接口，它支持序列化。public interface Serializable类通过实现 java.io.Serializable 接口以启用其序列化功能。
（2）HashTable的存储结构
private transient Entry
<?,?>[] table
;
private static class Entry<K,V> implements Map.Entry<K,V> {
final int hash
;
final K key
;
V value
;
Entry
<K,V> next
;
protected Entry(int hash
, K key
, V value
, Entry
<K,V> next
) {
this.hash
= hash
;
this.key
= key
;
this.value
= value
;
this.next
= next
;
}
}
从上面的结构可以看出。HashTable的存储结构与HashMap的存储结构相同
（3）HashTable的遍历方式
private class Enumerator<T> implements Enumeration<T>, Iterator
<T> { }
HashTable提供了两种遍历方式：
Enumeration<T>：利用枚举的方式从前向后遍历集合，不支持快速失败机制。Enumeration迭代器只能遍历Vector、Hashtable这种古老的集合，因此通常不要使用它，除非在某些极端情况下，不得不使用Enumeration，否则都应该选择Iterator迭代器。Iterator<T>：迭代器遍历方式。支持快速失败机制，目前使用较多的遍历方式。
3、HashTable源码分析
成员变量
{
private transient Entry
<?,?>[] table
;
private transient int count
;
private int threshold
;
private float loadFactor
;
private transient int modCount
= 0;
}
table：为一个Entry[]数组类型，Entry代表了“拉链”的节点，每一个Entry代表了一个键值对，哈希表的"key-value键值对"都是存储在Entry数组中的。count：HashTable的大小，注意这个大小并不是HashTable的容器大小，而是他所包含Entry键值对的数量。threshold：Hashtable的阈值，用于判断是否需要调整Hashtable的容量。threshold的值=“容量”。loadFactor：加载因子。modCount：用来实现“fail-fast”机制的（也就是快速失败）。所谓快速失败就是在并发集合中，其进行迭代操作时，若有其他线程对其进行结构性的修改，这时迭代器会立马感知到，并且立即抛出ConcurrentModificationException异常，而不是等到迭代完成之后才告诉你。
构造方法
默认构造函数，容量为11，加载因子为0.75。
public Hashtable() {
this(11, 0.75f);
}
用指定初始容量和默认的加载因子 (0.75) 构造一个新的空哈希表。
public Hashtable(int initialCapacity
) {
this(initialCapacity
, 0.75f);
}
用指定初始容量和指定加载因子构造一个新的空哈希表。其中initHashSeedAsNeeded方法用于初始化hashSeed参数，其中hashSeed用于计算key的hash值，它与key的hashCode进行按位异或运算。这个hashSeed是一个与实例相关的随机值，主要用于解决hash冲突。
public Hashtable(int initialCapacity
, float loadFactor
) {
if (initialCapacity
< 0)
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity
);
if (loadFactor
<= 0 || Float
.isNaN(loadFactor
))
throw new IllegalArgumentException("Illegal Load: "+loadFactor
);
if (initialCapacity
==0)
initialCapacity
= 1;
this.loadFactor
= loadFactor
;
table
= new Entry<?,?>[initialCapacity
];
threshold
= (int)Math
.min(initialCapacity
* loadFactor
, MAX_ARRAY_SIZE
+ 1);
}
构造一个与给定的 Map 具有相同映射关系的新哈希表。
public Hashtable(Map
<? extends K, ? extends V> t
) {
this(Math
.max(2*t
.size(), 11), 0.75f);
putAll(t
);
}
4、HashTable的常用操作
put方法 （注意这里键key和值value都不可为空）
public synchronized V
put(K key
, V value
) {
if (value
== null
) {
throw new NullPointerException();
}
Entry
<?,?> tab
[] = table
;
int hash
= key
.hashCode();
int index
= (hash
& 0x7FFFFFFF) % tab
.length
;
@SuppressWarnings("unchecked")
Entry
<K,V> entry
= (Entry
<K,V>)tab
[index
];
for(; entry
!= null
; entry
= entry
.next
) {
if ((entry
.hash
== hash
) && entry
.key
.equals(key
)) {
V old
= entry
.value
;
entry
.value
= value
;
return old
;
}
}
addEntry(hash
, key
, value
, index
);
return null
;
}
get方法
@SuppressWarnings("unchecked")
public synchronized V
get(Object key
) {
Entry
<?,?> tab
[] = table
;
int hash
= key
.hashCode();
int index
= (hash
& 0x7FFFFFFF) % tab
.length
;
for (Entry
<?,?> e
= tab
[index
] ; e
!= null
; e
= e
.next
) {
if ((e
.hash
== hash
) && e
.key
.equals(key
)) {
return (V
)e
.value
;
}
}
return null
;
}
remove方法
public synchronized V
remove(Object key
) {
Entry
<?,?> tab
[] = table
;
int hash
= key
.hashCode();
int index
= (hash
& 0x7FFFFFFF) % tab
.length
;
@SuppressWarnings("unchecked")
Entry
<K,V> e
= (Entry
<K,V>)tab
[index
];
for(Entry
<K,V> prev
= null
; e
!= null
; prev
= e
, e
= e
.next
) {
if ((e
.hash
== hash
) && e
.key
.equals(key
)) {
modCount
++;
if (prev
!= null
) {
prev
.next
= e
.next
;
} else {
tab
[index
] = e
.next
;
}
count
--;
V oldValue
= e
.value
;
e
.value
= null
;
return oldValue
;
}
}
return null
;
}
三：HashMap和HashTable的区别
HashTableHashMap
继承的父类不同DictionaryAbstractMap都实现了同时实现了map、Cloneable（可复制）、Serializable（可序列化）这三个接口都实现了同时实现了map、Cloneable（可复制）、Serializable（可序列化）这三个接口默认容量1116Table的初始化时机构造函数中初始化第一次put并发操作使用同步机制，实际应用程序中，仅仅是Hashtable本身的同步并不能保证程序在并发操作下的正确性，需要高层次的并发保护。下面的代码试图在key所对应的value值等于x的情况下修改value为x+1 { value = hashTable.get(key); if(value.intValue()== x){ hashTable.put(key, new Integer(value.intValue()+1)); } } 如2个线程同时执行以上代码，可能放入不是x+1，而是x+2.没有同步机制，需要使用者自己进行并发访问控制数据遍历的方式Iterator 和 EnumerationIterator是否支持fast-fail用Iterator遍历，支持fast-fail 用Enumeration不支持fast-fail支持fast-fail是否接受值为null的Key 或Value不接受接受根据hash值计算数组下标的算法没有扰动处理，哈希冲突重复率高，使用(hash & 0x7FFFFFFF) % tab.length;确保index为正数并且不会越界有扰动处理，哈希冲突重复率低，使用h & (length-1);确保index不会越界Entry数组的长度1116（并且始终为2的幂次方）LoadFactor负荷因子0.750.75负荷超过阈值时，内部数据的调整方式将容量变为原来的2倍加1将容量变为原来的2倍
