闲扯hashmap和hashtable

4.1 hashmap

在JDK1.8中，HashMap做了一些改变：

JDK1.7中，发生哈希碰撞时，将键值对添加到链表头部，JDK1.8是将键值对添加到链表尾部。

JDK1.8中，如果链表的长度超过8，将会将链表转化为红黑树。

容量的初始化：JDK1.7的HashMap在构造时会对容量进行初始化，而JDK1.8是在首次向HashMap总中执行put操作时，对容量进行初始化，也就是说，JDK1.8的HashMap使用了懒汉模式（在使用时才初始化），避免了初始化后却不用的资源浪费。

那为什么要进行树化的改造呢?

主要是为了避免哈希碰撞拒绝服务攻击。

从性能角度来看：解决哈希冲突时使用链表，插入和删除的效率很高，只需O(1)的时间复杂度，但对于查询而言，则需要O(n)的时间负责度。但红黑树的插入，删除，查询的最差时间复杂度为O(logn)。恶意代码可以利用大量数据与服务器交互，比如String的hashcode函数的强度很弱，有人可以很容易的构造出大量hashcode相同的String对象。如果向服务器一次提交数万个hashcode相同的字符串，服务器的查询时间过长，让服务器的CPU被大量占用，当有其他更多的请求时服务器会拒绝服务。而使用红黑树可以将查询时间降低到一定的数量级，可以有效避免哈希碰撞拒绝服务攻击。

---------------------

HashMap中对key求完hash值，在进行数组寻址时，使用的方法是位运算（代替的取模运算）。公式如下：

(length - 1) & hash // length为HashMap的容量，是2的n次方

在这里插播一个小知识点：位运算(&)比模运算(%)效率高很多，原因是位运算直接对内存数据进行操作，不需要像模运算一样转成十进制，因此处理速度快。

// 可以使用位运算代替模运算的原因，见以下公式：

hash % 2^n = hash & (2^n -1)

// 5 % 8 = 5 & 7 = 0110 & 0111 = 0110 = 5

// 13 % 8 = 13 & 7 = 1110 & 0111 = 0110 =5

Hashtable中求完hash值，在进行数组寻址时，使用的取模运算。公式如下：

int index = (hash & 0x7FFFFFFF) % tab.length;

// 此处hash和0x7FFFFFFF的一次位与操作，是为了保证得到的index值首位为0（代表正数），其实就是在取绝对值。以避免负数计算index的复杂度

// tab.length为Hashtable的长度。默认初始化为11，之后rehash每次扩容为oldCapacity * 2 + 1

前面说过，HashMap之所以不用取模的原因是为了提高效率，为什么Hashtable还要使用？有人认为，因为HashTable是个线程安全的类，本来就慢，所以Java并没有考虑效率问题，就直接使用取模算法了呢？但是其实并不完全是，Java这样设计还是有一定的考虑在的，虽然这样效率确实是会比HashMap慢一些。

HashTable简单的取模是有一定的考虑在的。这就要涉及到HashTable的构造函数和扩容函数。Hashtable的长度：默认初始化为11，之后rehash每次扩容为oldCapacity * 2 + 1。也就是说，HashTable的链表数组的默认大小是一个素数、奇数。之后的每次扩充结果也都是奇数。。

由于HashTable会尽量使用素数、奇数作为容量的大小。当哈希表的大小为素数时，简单的取模哈希的结果会更加均匀。这就是文章开头所提到的，问题来源

那为何hash要对素数取余呢？

常用的hash函数是选一个数m取模（余数），这个数在课本中推荐m是素数，但是经常见到选择m=2n，因为对2n求余数更快，并认为在key分布均匀的情况下，key%m也是在[0,m-1]区间均匀分布的。但实际上，key%m的分布同m是有关的。

证明如下： key%m = key - xm，即key减掉m的某个倍数x，剩下比m小的部分就是key除以m的余数。显然，x等于key/m的整数部分，以floor(key/m)表示。假设key和m有公约数g，即key=ag, m=bg, 则 key - xm = key - floor(key/m)m = key - floor(a/b)m。由于0 <= a/b <= a，所以floor(a/b)只有a+1中取值可能，从而推导出key%m也只有a+1中取值可能。a+1个球放在m个盒子里面，显然不可能做到均匀。

由此可知，一组均匀分布的key，其中同m公约数为1的那部分，余数后在[0,m-1]上还是均匀分布的，但同m公约数不为1的那部分，余数在[0, m-1]上就不是均匀分布的了。把m选为素数，正是为了让所有key同m的公约数都为1，从而保证余数的均匀分布，降低冲突率。

4.1 HashMap

哈希：

Hash，一般翻译做散列、杂凑，或音译为哈希，是把任意长度的输入（又叫做预映射pre-image）通过散列算法变换成固定长度的输出，该输出就是散列值。这种转换是一种压缩映射，也就是，散列值的空间通常远小于输入的空间，不同的输入可能会散列成相同的输出，所以不可能从散列值来确定唯一的输入值。简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。

哈希表：

闲扯hashmap和hashtable

常用哈希函数

散列函数能使对一个数据序列的访问过程更加迅速有效，通过散列函数，数据元素将被更快地定位。常用Hash函数有：

1．直接寻址法。取关键字或关键字的某个线性函数值为散列地址。即H(key)=key或H(key) = a·key + b，其中a和b为常数（这种散列函数叫做自身函数）

2．数字分析法。分析一组数据，比如一组员工的出生年月日，这时我们发现出生年月日的前几位数字大体相同，这样的话，出现冲突的几率就会很大，但是我们发现年月日的后几位表示月份和具体日期的数字差别很大，如果用后面的数字来构成散列地址，则冲突的几率会明显降低。因此数字分析法就是找出数字的规律，尽可能利用这些数据来构造冲突几率较低的散列地址。

3．平方取中法。取关键字平方后的中间几位作为散列地址。

4．折叠法。将关键字分割成位数相同的几部分，最后一部分位数可以不同，然后取这几部分的叠加和（去除进位）作为散列地址。

5．随机数法。选择一随机函数，取关键字作为随机函数的种子生成随机值作为散列地址，通常用于关键字长度不同的场合。

6．除留余数法。取关键字被某个不大于散列表表长m的数p除后所得的余数为散列地址。即 H(key) = key MOD p,p<=m。不仅可以对关键字直接取模，也可在折叠、平方取中等运算之后取模。对p的选择很重要，一般取素数或m，若p选的不好，容易产生碰撞。

java的string的hashcode实现
public int hashCode() {
int h = hash;//hash 默认是 0
if (h == 0 && value.length > 0) { // 只算一次
char val[] = value;
for (int i = 0; i < value.length; i++) {
h = 31 * h + val[i];
}
hash = h;
}
return h;
}

java的object的hashcode实现：

哈希冲突处理方法：

1．开放寻址法；Hi=(H(key) + di) MOD m,i=1,2,…，k(k<=m-1)，其中H(key)为散列函数，m为散列表长，di为增量序列，可有下列三种取法：

1)． di=1,2,3,…，m-1，称线性探测再散列；

2)． di=1^2,-1^2,2^2,-2^2,3^2,…，±k^2,(k<=m/2)称二次探测再散列；

3)． di=伪随机数序列，称伪随机探测再散列。

2．再散列法：Hi=RHi(key),i=1,2,…，k RHi均是不同的散列函数，即在同义词产生地址冲突时计算另一个散列函数地址，直到冲突不再发生，这种方法不易产生“聚集”，但增加了计算时间。

3．链地址法(拉链法)

4．建立一个公共溢出区

package java.util;

import java.io.IOException;

import java.io.InvalidObjectException;

import java.io.Serializable;

import java.lang.reflect.ParameterizedType;

import java.lang.reflect.Type;

import java.util.function.BiConsumer;

import java.util.function.BiFunction;

import java.util.function.Consumer;

import java.util.function.Function;

import sun.misc.SharedSecrets;

public class HashMap<K,V> extends AbstractMap<K,V>

implements Map<K,V>, Cloneable, Serializable {

private static final long serialVersionUID = 362498820763181265L;

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

static final int MAXIMUM_CAPACITY = 1 << 30;

static final float DEFAULT_LOAD_FACTOR = 0.75f;//为什么是0.75

static final int TREEIFY_THRESHOLD = 8;

static final int UNTREEIFY_THRESHOLD = 6;

static final int MIN_TREEIFY_CAPACITY = 64;

/* ---------------- Fields -------------- */

transient Node<K,V>[] table; //数组

transient Set<Map.Entry<K,V>> entrySet;

transient int size;

transient int modCount;

int threshold;

final float loadFactor;

static class Node<K,V> implements Map.Entry<K,V> {

final int hash;

final K key;

V value;

Node<K,V> next;

Node(int hash, K key, V value, Node<K,V> next) {

this.hash = hash;

this.key = key;

this.value = value;

this.next = next;

}

public final K getKey() { return key; }

public final V getValue() { return value; }

public final String toString() { return key + "=" + value; }

//object 的hash函数

public final int hashCode() {

return Objects.hashCode(key) ^ Objects.hashCode(value);

}

public final V setValue(V newValue) {

V oldValue = value;

value = newValue;

return oldValue;

}

public final boolean equals(Object o) {

if (o == this)

return true;

if (o instanceof Map.Entry) {

Map.Entry<?,?> e = (Map.Entry<?,?>)o;

if (Objects.equals(key, e.getKey()) &&

Objects.equals(value, e.getValue()))

return true;

}

return false;

}

/* ---------------- Static utilities -------------- */

static final int hash(Object key) {

int h;

return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);

}

/* ---------------- Public operations -------------- */

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;

this.threshold = tableSizeFor(initialCapacity);

}

public HashMap(int initialCapacity) {

this(initialCapacity, DEFAULT_LOAD_FACTOR);

}

public HashMap() {

this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted

}

public HashMap(Map<? extends K, ? extends V> m) {

this.loadFactor = DEFAULT_LOAD_FACTOR;

putMapEntries(m, false);

}

final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {

int s = m.size();

if (s > 0) {

if (table == null) { // pre-size

float ft = ((float)s / loadFactor) + 1.0F;

int t = ((ft < (float)MAXIMUM_CAPACITY) ?

(int)ft : MAXIMUM_CAPACITY);

if (t > threshold)

threshold = tableSizeFor(t);

}

else if (s > threshold)

resize();

for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {

K key = e.getKey();

V value = e.getValue();

putVal(hash(key), key, value, false, evict);

}

public int size() {

return size;

}

public boolean isEmpty() {

return size == 0;

}

public V get(Object key) {

Node<K,V> e;

return (e = getNode(hash(key), key)) == null ? null : e.value;

}

final Node<K,V> getNode(int hash, Object key) {

Node<K,V>[] tab; Node<K,V> first, e; int n; K k;

if ((tab = table) != null && (n = tab.length) > 0 &&

(first = tab[(n - 1) & hash]) != null) {

if (first.hash == hash && // always check first node

((k = first.key) == key || (key != null && key.equals(k))))

return first;

if ((e = first.next) != null) {

if (first instanceof TreeNode)

return ((TreeNode<K,V>)first).getTreeNode(hash, key);

do {

if (e.hash == hash &&

((k = e.key) == key || (key != null && key.equals(k))))

return e;

} while ((e = e.next) != null);

}

return null;

}

public boolean containsKey(Object key) {

return getNode(hash(key), key) != null;

}

public V put(K key, V value) {

return putVal(hash(key), key, value, false, true);

}

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,

boolean evict) {

Node<K,V>[] tab; Node<K,V> p; int n, i;

if ((tab = table) == null || (n = tab.length) == 0)

n = (tab = resize()).length;

if ((p = tab[i = (n - 1) & hash]) == null)

tab[i] = newNode(hash, key, value, null);

else {

Node<K,V> e; K k;

if (p.hash == hash &&

((k = p.key) == key || (key != null && key.equals(k))))

e = p;

else if (p instanceof TreeNode)

e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);

else {

for (int binCount = 0; ; ++binCount) {

if ((e = p.next) == null) {

p.next = newNode(hash, key, value, null);

if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st

treeifyBin(tab, hash);

break;

}

if (e.hash == hash &&

((k = e.key) == key || (key != null && key.equals(k))))

break;

p = e;

}

if (e != null) { // existing mapping for key

V oldValue = e.value;

if (!onlyIfAbsent || oldValue == null)

e.value = value;

afterNodeAccess(e);

return oldValue;

}

++modCount;

if (++size > threshold)

resize();

afterNodeInsertion(evict);

return null;

}

final Node<K,V>[] resize() {

Node<K,V>[] oldTab = table;

int oldCap = (oldTab == null) ? 0 : oldTab.length;

int oldThr = threshold;

int newCap, newThr = 0;

if (oldCap > 0) {

if (oldCap >= MAXIMUM_CAPACITY) {

threshold = Integer.MAX_VALUE;

return oldTab;

}

else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&

oldCap >= DEFAULT_INITIAL_CAPACITY)

newThr = oldThr << 1; // double threshold

}

else if (oldThr > 0) // initial capacity was placed in threshold

newCap = oldThr;

else { // zero initial threshold signifies using defaults

newCap = DEFAULT_INITIAL_CAPACITY;

newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);

}

if (newThr == 0) {

float ft = (float)newCap * loadFactor;

newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?

(int)ft : Integer.MAX_VALUE);

}

threshold = newThr;

@SuppressWarnings({"rawtypes","unchecked"})

Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];

table = newTab;

if (oldTab != null) {

for (int j = 0; j < oldCap; ++j) {

Node<K,V> e;

if ((e = oldTab[j]) != null) {

oldTab[j] = null;

if (e.next == null)

newTab[e.hash & (newCap - 1)] = e;

else if (e instanceof TreeNode)

((TreeNode<K,V>)e).split(this, newTab, j, oldCap);

else { // preserve order

Node<K,V> loHead = null, loTail = null;

Node<K,V> hiHead = null, hiTail = null;

Node<K,V> next;

do {

next = e.next;

if ((e.hash & oldCap) == 0) {

if (loTail == null)

loHead = e;

else

loTail.next = e;

loTail = e;

}

else {

if (hiTail == null)

hiHead = e;

else

hiTail.next = e;

hiTail = e;

}

} while ((e = next) != null);

if (loTail != null) {

loTail.next = null;

newTab[j] = loHead;

}

if (hiTail != null) {

hiTail.next = null;

newTab[j + oldCap] = hiHead;

}

return newTab;

}

final void treeifyBin(Node<K,V>[] tab, int hash) {

int n, index; Node<K,V> e;

if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)

resize();

else if ((e = tab[index = (n - 1) & hash]) != null) {

TreeNode<K,V> hd = null, tl = null;

do {

TreeNode<K,V> p = replacementTreeNode(e, null);

if (tl == null)

hd = p;

else {

p.prev = tl;

tl.next = p;

}

tl = p;

} while ((e = e.next) != null);

if ((tab[index] = hd) != null)

hd.treeify(tab);

}

4.2hashtable

package java.util;

import java.io.*;

import java.util.concurrent.ThreadLocalRandom;

import java.util.function.BiConsumer;

import java.util.function.Function;

import java.util.function.BiFunction;

import sun.misc.SharedSecrets;

public class Hashtable<K,V>

extends Dictionary<K,V>

implements Map<K,V>, Cloneable, java.io.Serializable {

private transient Entry<?,?>[] table;

private transient int count;

private int threshold;

private float loadFactor;

private transient int modCount = 0;

private static final long serialVersionUID = 1421746759512286392L;

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

}

public Hashtable(int initialCapacity) {

this(initialCapacity, 0.75f);

}

public Hashtable() {

this(11, 0.75f);

}

public Hashtable(Map<? extends K, ? extends V> t) {

this(Math.max(2*t.size(), 11), 0.75f);

putAll(t);

}

public synchronized int size() {

return count;

}

public synchronized boolean isEmpty() {

return count == 0;

}

public synchronized Enumeration<K> keys() {

return this.<K>getEnumeration(KEYS);

}

public synchronized Enumeration<V> elements() {

return this.<V>getEnumeration(VALUES);

}

public synchronized boolean contains(Object value) {

if (value == null) {

throw new NullPointerException();

}

Entry<?,?> tab[] = table;

for (int i = tab.length ; i-- > 0 ;) {

for (Entry<?,?> e = tab[i] ; e != null ; e = e.next) {

if (e.value.equals(value)) {

return true;

}

return false;

}

public boolean containsValue(Object value) {

return contains(value);

}

public synchronized boolean containsKey(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 true;

}

return false;

}

//先计算key的hash，得到数组下表，然后得到value

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

}

private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

// HashTable中，当key值的数量达到阀值时，需要重新扩展容器数量。调用rehash方法，扩展容器的大小。

hashTable是一个数组的链表，本身是一个 Entry[] 数组，里面的一个对象放的是一个链表的结构。如果一个HashTable中key的hashcode相同，那么它就放在同一个链表中。

回到rehash中，在扩展容器本身的容量时，每个对象（key,value）的位置也会相应的发生调整

@SuppressWarnings("unchecked")

protected void rehash() {

int oldCapacity = table.length;

Entry<?,?>[] oldMap = table;

// overflow-conscious code

int newCapacity = (oldCapacity << 1) + 1;

if (newCapacity - MAX_ARRAY_SIZE > 0) {

if (oldCapacity == MAX_ARRAY_SIZE)

// Keep running with MAX_ARRAY_SIZE buckets

return;

newCapacity = MAX_ARRAY_SIZE;

}

Entry<?,?>[] newMap = new Entry<?,?>[newCapacity];

modCount++;

threshold = (int)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1);

table = newMap;

for (int i = oldCapacity ; i-- > 0 ;) {

for (Entry<K,V> old = (Entry<K,V>)oldMap[i] ; old != null ; ) {

Entry<K,V> e = old;

old = old.next;

int index = (e.hash & 0x7FFFFFFF) % newCapacity;

e.next = (Entry<K,V>)newMap[index];

newMap[index] = e;

}

private void addEntry(int hash, K key, V value, int index) {

modCount++;

Entry<?,?> tab[] = table;

if (count >= threshold) {

// Rehash the table if the threshold is exceeded

rehash();

tab = table;

hash = key.hashCode();

index = (hash & 0x7FFFFFFF) % tab.length;

}

// Creates the new entry.

@SuppressWarnings("unchecked")

Entry<K,V> e = (Entry<K,V>) tab[index];

tab[index] = new Entry<>(hash, key, value, e);

count++;

}

//hashtable存值

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的hash值

int index = (hash & 0x7FFFFFFF) % tab.length;//计算key放入数组的index

@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);//把key和value分别录入值

return null;

}

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

相关推荐