以前一直用hash表，但是并不清楚它的原理。所以，我决定手写一个hash表，彻底搞清它的工作方式。这里有一个误区是：通常我们会认为对象数组是存储对象本身，也就是对象数组是开辟一个空间，然后将对象放进去。这不仅从jvm的角度来解释（java对象创建在堆上），而且自己认真想想就不是这样。对象数组其实保存的是对象的引用而已。为什么要说这么简单的事，因为当初确实理解这个hashmap的时候搞糊涂了。有一段代码可以证明保存的是引用：
/**
*最后输出的是“改变”，说明存储的是内存地址（不然没有修改数组中的对象数组中对象为什么会发生改变）
*/
public class TestArray {
public static void main(String[] args) {
Item[] items = new Item[3];
Item item = new Item();
item.setName("123");
items[0] = item;
item.setName("改变");
System.out.println(items[0].getName());
}
}
class Item {
private String name;
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
@Override
public String toString() {
return "Item{" +
"name='" + name + '\'' +
'}';
}
}
说到hash表，其实他是通过一个函数输入key算value的地址在哪。业界采用的比较多的方式是链地址法。
链地址法.png
这里只是说了个大概的结构，如果想要看详细的过程，可以看这里
这个方法的好处是，结合了数组和链表的优势，抵消hash冲突带来的劣势。每个链表节点都有key,value,next节点。工作流程：先通过key算地址得到f(key)，找到链表的头，然后将key的值与每个节点key的值比较，如果key相同，将value值返回。
代码如下：
class entry<k, v>{
int capacity;
node[] no;
public entry(int n){
capacity = n;
no = new node[n];
}
//链表类
class node<k, v>{
k key;
v value;
node<k, v> next;
public node(){}
node(k key, v value, node<k, v> next){
this.key = key;
this.value = value;
this.next = next;
}
}
public int hashcode(k key){
return (key.hashCode() & 0x7ffffff) % capacity;
}
public void put(k key, v value){
int h = hashcode(key);
for(node<k, v> n = no[h]; n != null; n = n.next){
if(key.equals(n.key)){
n.value = value;
return;
}
}
node<k, v> old = no[h];//插入的时候应该是这么插，将新节点的地址放到数组中，然后让新节点指向原来第一个节点
no[h] = new node(key, value, old);
}
public v get(k key){
int h = hashcode(key);
if(no[h] == null){
return null;
}
for(node<k, v> n = no[h]; n != null; n = n.next){
if(key.equals(n.key))
return n.value;
}
return null;
}
public static void main(String[] args) {
entry<Integer, Integer> map = new entry<Integer, Integer>(100);
map.put(1, 90);
map.put(2, 95);
System.out.println(map.get(1));
System.out.println(map.get(2));
}
}
