哈希表：是一种根据关键码去寻找值的数据映射结构，该结构通过把关键码映射的位置去寻找存放值的地方
哈希表图（哈希表相当于数组加链表）Java手工实现HashMap：
Node2.java 如下
package cn.zhazong710.test;
//用于哈希表
public class Node2<K,V> {
int hash;
K key;
V value;
Node2 next;
}
ZZHashMap.java 如下
package cn.zhazong710.test;
public class ZZHashMap<K,V> {
Node2[] table; //位桶数组
int size; //存放键值对的个数
public ZZHashMap() { //哈希表
table = new Node2[16]; //长度一般定义为2的整数幂
}
public V get(K key) {
int hash = myHash(key.hashCode(),table.length);
V value = null;
if(table[hash]!=null) {
Node2 temp = table[hash];
while(temp!=null) {
if(temp!=null) {
value = (V)temp.value;
break;
}else{
temp = temp.next;
}
}
}
return value;
}
public void put(K key, V value) { //定义新节点对象
Node2 newNode = new Node2();
newNode.hash = myHash(key.hashCode(), table.length);
newNode.key = key;
newNode.value = value;
newNode.next = null;
Node2 temp = table[newNode.hash];
Node2 iterLast = null; //正在遍历的最后一个元素
boolean keyRepeat = false;
if(temp==null) { //此处数组元素为空，直接放入新节点
table[newNode.hash] = newNode;
size++;
}else { //此处数组元素不为空，遍历对应链表
while(temp!=null) {
if(temp.key.equals(key)) { //判断key重复，直接覆盖value
keyRepeat = true;
temp.value = value;
break;
}else { //key不重复，遍历下一个
iterLast = temp;
temp = temp.next;
}
}
if(!keyRepeat) { //如果没有发生key重复，添加最后链表
iterLast.next = newNode;
size++;
}
}
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder("{");
for(int i=0;i<table.length;i++) { //遍历bucket数组
Node2 temp = table[i];
while(temp!=null) { //遍历链表
sb.append(temp.key+":"+temp.value+",");
temp = temp.next;
}
}
sb.setCharAt(sb.length()-1, '}');
return sb.toString();
}
public static void main(String[] args) {
ZZHashMap<Integer,String> m = new ZZHashMap<>();
m.put(10, "a");
m.put(20, "b");
m.put(30, "c");
System.out.println(m);
System.out.println(m.get(20));
}
public int myHash(int v, int length) { //哈希值运算
//System.out.println(v&(length-1)); //位运算效率高
//System.out.println(v%(length-1)); //取模运算效率低
return v&(length-1);
}
}
