通过key计算二次哈希值，然后哈希值与数组长度进行与运算
总结：
得到的结果便是数组的下标
通过该种索引方法可以实现查询优化
通过key计算二次哈希值，然后哈希值与数组长度进行与运算
得到的结果便是数组的下标
通过该种索引方法可以实现查询优化
自己实现的简单SimpleHashMap
//
import java.util.Map;
import java.util.Objects;
/**
*
* @author Naah
*
* @param 键
* @param 值
*/
public class SimpleHashMap<K, V> {
// 链表数组
Entry<K, V>[] table = null;
// 默认数组大小
final int DEFAULT_INITIAL_ARRAY_CAPACITY = 1 << 4;
// 最大容量
final int MAXIMUM_CAPACITY = 1 << 30;
// 装载因子
double loadFactor = 0.75;
// 扩容系数
int expansionMultiple = 2;
// 节点临界值
int threshold = 160;
// 数据数量
int size;
// 哈希因子
int hashSeed = 0;
/**
* 自定义HashMap构造函数
* @param loadFactor 装载因子,用于判定是否需要扩容数组，该数越大，扩容频率越低
* @param expansionMultiple 扩容系数，扩容时的增长系数
* @param threshold 节点临界值，用于判定是否需要扩容数组，该数越大，扩容频率越低
*/
public SimpleHashMap(double loadFactor, int expansionMultiple, int threshold) {
super();
this.loadFactor = loadFactor <= 0 ? this.loadFactor : loadFactor;
this.expansionMultiple = expansionMultiple <= 0 ? this.expansionMultiple
: expansionMultiple;
this.threshold = threshold <= 0 ? this.threshold : threshold;
}
/**
* 默认构造函数
*/
public SimpleHashMap() {
super();
}
/**
* 添加元素方法
* @param key 键
* @param value 值
* @return 覆盖则返回原值,添加则返回空
*/
public V put(K key, V value) {
// 数组为空或数量大于临界值乘以装载因子时进行扩容
if (table == null || size >= threshold * loadFactor) {
expansion();
}
// 获取哈希值及索引号
int hash = key == null ? 0 : hash(key);
int index = indexFor(hash, table.length);
// 通过索引号选择数组位置，遍历链表
for (Entry<K, V> e = table[index]; e != null; e = e.next) {
// 如果有该键则进行覆盖
if (e.hash == hash
&& (key == null && e.key == null || (e.key).equals(key))) {
V oldValue = e.value;
e.value = value;
// 返回原值
return oldValue;
}
}
// 添加新元素
addEntry(key, value, hash, index);
return null;
}
/**
* 添加元素方法
* @param key 键
* @param value 值
* @param hash 哈希值
* @param index 索引号
*/
private void addEntry(K key, V value, int hash, int index) {
// 取出原头节点
Entry<K, V> head = table[index];
// 将原头结点作为新节点的后继
Entry<K, V> entry = new Entry<K, V>(hash, key, value, head);
// 将新节点设置为头节点
table[index] = entry;
// 增加数量
size++;
}
/**
* 取值方法
* @param key 键
* @return 值
*/
public V get(K key) {
// 获取哈希值以及索引号
int hash = key == null ? 0 : hash(key);
int index = indexFor(hash, table.length);
// 通过索引号选择链表进行遍历
for (Entry<K, V> e = table[index]; e != null; e = e.next) {
// 哈希值以及键相同
if (e.hash == hash
&& (key == null && e.key == null || (e.key).equals(key))) {
// 返回值
return e.value;
}
}
return null;
}
/**
* 移除方法
* @param key 键
* @return 值
*/
public V remove(K key) {
// 获取哈希值以及索引号
int hash = key == null ? 0 : hash(key);
int index = indexFor(hash, table.length);
// 取出头节点
Entry<K, V> prev = table[index];
// 通过索引号选择链表进行
// prev为前驱
// e为目前节点
for (Entry<K, V> e = table[index]; e != null; prev = e, e = e.next) {
// 哈希值相同并且键相同
if (e.hash == hash
&& (key == null && e.key == null || (e.key).equals(key))) {
// 如果该节点为头节点
if (e == prev && e.equals(prev)) {
// 将该节点的后继设置为头节点
table[index] = e.next;
} else {
// 将前驱的后继设置为该节点的后继
prev.next = e.next;
}
}
// 减少数量
size--;
// 返回值
return e.value;
}
// 找不到返回空
return null;
}
/**
* 扩容函数
*/
private void expansion() {
// 如果目前数组为空
if (table == null) {
// 创建一个默认容量的数组
table = new Entry[DEFAULT_INITIAL_ARRAY_CAPACITY];
} else {
// 如果当前数据数量大于最大值则设置为最大值，否则设置数组长度为当前数组长度*扩容系数
Entry<K, V>[] newTable = new Entry[size >= MAXIMUM_CAPACITY ? MAXIMUM_CAPACITY
: table.length * expansionMultiple];
// 将临界值设置为数组长度的10倍
threshold = newTable.length * 10;
// 转移数据
trans(newTable);
// 将新数组设置为当前数组
table = newTable;
}
}
/**
* 转移数据方法
* @param newTable 新数组
*/
private void trans(Entry<K, V>[] newTable) {
// 遍历原数组
for (Entry<K, V> entry : table) {
Entry<K, V> next;
// 遍历当前链表
for (; entry != null; entry = next) {
// 获得哈希值与新的索引号
int hash = entry.key == null ? 0 : hash(entry.key);
int index = indexFor(hash, newTable.length);
// 将当前元素的后继暂存
next = entry.next;
// 将当前元素的后继设置为指定索引链表头结点
entry.next = newTable[index];
// 将当前节点设置为指定索引链表头结点
newTable[index] = entry;
}
}
}
/**
* 哈希值方法
* @param k 键
* @return 哈希值
*/
private final int hash(Object k) {
// 获取哈希种子
int h = hashSeed;
h ^= k.hashCode();
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
/**
* 索引号方法
* @param h 哈希值
* @param length 长度
* @return
*/
private static int indexFor(int h, int length) {
// 通过与运算获取不大于数组长度的索引号
return h & (length - 1);
}
/**
* 节点类
* @author HashMap
*
* @param 键
* @param 值
*/
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;
}
public final K getKey() {
return key;
}
public final V getValue() {
return value;
}
public final V setValue(V newValue) {
V oldValue = value;
value = newValue;
return oldValue;
}
public final boolean equals(Object o) {
if (!(o instanceof Map.Entry))
return false;
Map.Entry e = (Map.Entry) o;
Object k1 = getKey();
Object k2 = e.getKey();
if (k1 == k2 || (k1 != null && k1.equals(k2))) {
Object v1 = getValue();
Object v2 = e.getValue();
if (v1 == v2 || (v1 != null && v1.equals(v2)))
return true;
}
return false;
}
public final int hashCode() {
return Objects.hashCode(getKey()) ^ Objects.hashCode(getValue());
}
public final String toString() {
return getKey() + "=" + getValue();
}
}
}
