# 1 为什么要用散列值？

public class SlowMap<K,V> extends AbstractMap<K,V> {
private List<K> keys = new ArrayList<K>();
private List<V> values = new ArrayList<V>();
public V put(K key, V value) {
V oldValue = get(key); // The old value or null
if(!keys.contains(key)) {
} else
values.set(keys.indexOf(key), value);
return oldValue;
}
public V get(Object key) { // key is type Object, not K
if(!keys.contains(key))
return null;
return values.get(keys.indexOf(key));
}
public Set<Map.Entry<K,V>> entrySet() {
Set<Map.Entry<K,V>> set= new HashSet<Map.Entry<K,V>>();
Iterator<K> ki = keys.iterator();
Iterator<V> vi = values.iterator();
while(ki.hasNext())
return set;
}
public static void main(String[] args) {
SlowMap<String,String> m= new SlowMap<String,String>();
m.putAll(Countries.capitals(15));
System.out.println(m);
System.out.println(m.get("BULGARIA"));
System.out.println(m.entrySet());
}
}


# 2 为速度而生的散列码：

public class SimpleHashMap<K,V> extends AbstractMap<K,V> {
// Choose a prime number for the hash table
// size, to achieve a uniform distribution:
static final int SIZE = 997;
// You can't have a physical array of generics,
// but you can upcast to one:
@SuppressWarnings("unchecked")
public V put(K key, V value) {
V oldValue = null;
int index = Math.abs(key.hashCode()) % SIZE;
if(buckets[index] == null)
MapEntry<K,V> pair = new MapEntry<K,V>(key, value);
boolean found = false;
ListIterator<MapEntry<K,V>> it = bucket.listIterator();
while(it.hasNext()) {
MapEntry<K,V> iPair = it.next();
if(iPair.getKey().equals(key)) {
oldValue = iPair.getValue();
it.set(pair); // Replace old with new
found = true;
break;
}
}
if(!found)
return oldValue;
}
public V get(Object key) {
int index = Math.abs(key.hashCode()) % SIZE;
if(buckets[index] == null) return null;
for(MapEntry<K,V> iPair : buckets[index])
if(iPair.getKey().equals(key))
return iPair.getValue();
return null;
}
public Set<Map.Entry<K,V>> entrySet() {
Set<Map.Entry<K,V>> set= new HashSet<Map.Entry<K,V>>();
if(bucket == null) continue;
for(MapEntry<K,V> mpair : bucket)
}
return set;
}
}


1. 以散列码为下标的数组被称为散列表，散列表的中位置被称为桶位（bucket）,桶排序也和桶位有关，故此得名；

# 3 如何覆盖hashCode()方法

1. 同一个对象无论何时调用hashCode方法都应该生成同样的散列码，因此不能依赖对象中易变数据生成散列码。
2. hashCode方法也尽量不能完全依赖具有唯一性的信息，比如默认this值，默认hashCode方法就是返回对象存储地址，这样做虽然保证了每个对象都是不同的散列码，但是该散列码没有意义，两个逻辑上相同的对象（比如内容相同String类对象）也会生成不同的散列码，所以生成散列码需要依赖对象的有意义的信息
3. hashCode方法和equal方法等价，也就是说调用equal方法相等的两个对象，其散列值也应该是相同的，反之也成立。
4. hashCode方法运算过程不能太复杂，因为散列码是为了追求速度而设计的，所有不能在生成散列码的过程中过度浪费时间；
5. 散列码应该尽量均匀分布，以减少在线性查询过程的平均时间；

《Effective Java》给出了一种实现hashCode的指导方法：

1. 对于int变量result = 某个非0的变量，比如17；
2. 为对象内每个有意义的域f（也就是在执行equal方法时需要对比的域），计算出一个int散列码c:

boolean c = f ? 0 : 1
byte、 char、short、int c = (int)f
long c = (int)(f^(f>>32))
float c = Float.floatToIntBits(f)
double 将其转化为long型，再计算
Object对象 c = f.hashCode()

1. 依次迭代计算散列码：
result = 37* result + c ;
2. 返回result
3. 确定相等的实例具有相同散列码，反之也要成立。

public class CountedString {
private static List<String> created =
new ArrayList<String>();
private String s;
private int id = 0;
public CountedString(String str) {
s = str;
// id is the total number of instances
// of this string in use by CountedString:
for(String s2 : created)
if(s2.equals(s))
id++;
}
public String toString() {
return "String: " + s + " id: " + id +
" hashCode(): " + hashCode();
}
public int hashCode() {
// The very simple approach:
// return s.hashCode() * id;
// Using Joshua Bloch's recipe:
int result = 17;
result = 37 * result + s.hashCode();
result = 37 * result + id;
return result;
}
public boolean equals(Object o) {
return o instanceof CountedString &&
s.equals(((CountedString)o).s) &&
id == ((CountedString)o).id;
}
}


# 4 HashMap源码分析

## 4.1 HashMap基础

    /**
* The default initial capacity - MUST be a power of two.
*/
static final int DEFAULT_INITIAL_CAPACITY = 16;
/**
* The table, resized as necessary. Length MUST Always be a power of two.
*/
transient Entry<K,V>[] table;


    /**
* The next size value at which to resize (capacity * load factor).
* @serial
*/
int threshold;

/**
* The load factor for the hash table.
*
* @serial
*/

/**
* The load factor used when none specified in constructor.
*/
static final float DEFAULT_LOAD_FACTOR = 0.75f;


static class Entry<K,V> implements Map.Entry<K,V> {
final K key;
V value;
Entry<K,V> next;
int hash;

/**
* Creates new entry.
*/
Entry(int h, K k, V v, Entry<K,V> n) {
value = v;
next = n;
key = k;
hash = h;
}
.......
}


## 4.2 put方法

public V put(K key, V value) {
//1. 如果键为null,则进入key为null的流程
if (key == null)
return putForNullKey(value);
//2. 获取key的散列值，二次散列
int hash = hash(key);
//3. 根据散列码确定在散列表中的位置
int i = indexFor(hash, table.length);
//4. 如果能在散列表中找到对应的键值对，则更新
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;
}
}

//5. 没能找到键值对，则创建加入该键值对
modCount++;
return null;
}


1. 由于HashMap允许key为空，所以当发现key==null时，调用方法putForNullKey
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++;
return null;
}


1. 当确定key不为空后，就开始计算key的散列码：
    //2. 获取key的散列值，二次散列
int hash = hash(key);


final int hash(Object k) {
//散列码初始值
int h = 0;
//1. 是否启动改进散列值模式；
if (useAltHashing) {
if (k instanceof String) {
return sun.misc.Hashing.stringHash32((String) k);
}
h = hashSeed;
}
//2. 获得第一次散列码；
h ^= k.hashCode();

//3. 防止因散列表大小为2的幂次而造成的散列碰撞；
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}

• 因为Sun公司提供了增强的计算散列码的方法，如果当前配置环境支持这种选择，就可以启动增强模式。该模式下，String类型的散列码已经直接可以得到；而对于其他类型，也挺通过了一个散列种子hashSeed来帮助减少散列碰撞的发生。
• 第一次散列，是通过Key本身的散列函数完成；
• 第二次散列是为了减少因散列表大小为2的幂次而造成的散列碰撞。

0101 0000 0000 1111 = 20495
0111 0000 0000 1111 = 28687

1. 获得散列码之后，使用散列码确定该值其在散列表中的位置：
/**
* Returns index for hash code h.
*/
static int indexFor(int h, int length) {
return h & (length-1);
}


1. 确定元素在散列表中位置后，就开始查找外部链表中是否包含该key，请注意key是否存在的条件
e.hash == hash && ((k = e.key) == key || key.equals(k))


1. 如果没有找到该Key，就会添加一个键值对条目。在添加新条目之前，会执行modCount++。modCount的定义如下：
/**
* The number of times this HashMap has been structurally modified
* Structural modifications are those that change the number of mappings in
* the HashMap or otherwise modify its internal structure (e.g.,
* rehash).  This field is used to make iterators on Collection-views of
* the HashMap fail-fast.  (See ConcurrentModificationException).
*/
transient int modCount;


if (modCount != expectedModCount)
throw new ConcurrentModificationException();


void addEntry(int hash, K key, V value, int bucketIndex) {
// 如果散列表的数量已经阈值就开始扩容散列表
if ((size >= threshold) && (null != table[bucketIndex])) {
//扩容2倍
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++;
}


## 4.3 containsKey方法

public boolean containsKey(Object key) {
return getEntry(key) != null;
}

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;
}


#### 9.4.4 get方法

get操作时HashMap中使用频率最高的，其实现和containsKey方法一样都是基于getEntry方法：

public V get(Object key) {
//1. 如果key为空，则尝试获取NullKey位置的条目
if (key == null)
return getForNullKey();
//2. 根据key获得条目
Entry<K,V> entry = getEntry(key);
//3. 返回条目；
return null == entry ? null : entry.getValue();
}

private V getForNullKey() {
//空key的桶位默认为0
for (Entry<K,V> e = table[0]; e != null; e = e.next) {
if (e.key == null)
return e.value;
}
return null;
}


+ 订阅