jdk的hashmap悄谐，當(dāng)然比較完美，這里寫一個(gè)簡(jiǎn)單的hashmap库北。
第一版本：
1爬舰、hash算法沒有hashmap好。
2寒瓦、數(shù)組長(zhǎng)度沒有做到2的n次方情屹。
3、沒有jdk8的紅黑樹杂腰。
4垃你、擴(kuò)容算法，直接粗暴的重新放到新數(shù)組喂很，做了一些無用功惜颇，比如，擴(kuò)容放元素的時(shí)候少辣，是不需要比較的凌摄，可以直接放置在鏈表的頭部，不需要一個(gè)一個(gè)遍歷比較漓帅，然后放到尾部锨亏。
4、等等忙干。
public class DiyHashMap<K, V> {
private DiyHashMap.Node[] nodes;
private int size;
private Integer threshold;
private Float rate;
private Integer length;
public DiyHashMap(Integer length, Float rate) {
this.length = length;
this.rate = rate;
Float temp = length * rate;
this.threshold = temp.intValue();
}
private class Node {
private K key;
private V value;
private Node next;
public Node(K key, V value) {
this.key = key;
this.value = value;
}
}
public void put(K k, V v) {
if (nodes == null) {
nodes = new DiyHashMap.Node[length];
}
if (size >= threshold) {
// 擴(kuò)容
resize();
}
Node node = new Node(k, v);
int index = indexOfArray(k.hashCode());
if (nodes[index] == null) {
nodes[index] = node;
size++;
} else {
// 鏈表查找
Node n = nodes[index];
while (true) {
if (n.next == null) {
// 直接隊(duì)列尾放置
n.next = node;
size++;
break;
} else if (n.next.key.hashCode() == k.hashCode() && n.next.key.equals(k)) {
// 替換
n.next.value = v;
break;
} else {
// 往下遍歷
n = n.next;
}
}
}
}
public void resize() {
int newLength = length << 1;
this.length = newLength;
Float temp = length * rate;
this.threshold = temp.intValue();
this.size = 0;
Node[] oldNodes = nodes;
DiyHashMap.Node[] newNodes = new DiyHashMap.Node[newLength];
this.nodes = newNodes;
for (int i = 0; i < oldNodes.length; i++) {
Node oldNode = oldNodes[i];
while (true) {
if (oldNode != null) {
this.put(oldNode.key, oldNode.value);
oldNode = oldNode.next;
} else {
break;
}
}
}
}
public int indexOfArray(int hashcode) {
int i = hashcode % length;
if(i < 0){
return 0 - i;
}
return i;
}
public V get(K k) {
int index = indexOfArray(k.hashCode());
Node node = nodes[index];
while (true) {
if (node == null) {
return null;
} else if (node.key.hashCode() == k.hashCode() && node.key.equals(k)) {
// 找到了
return node.value;
} else {
node = node.next;
}
}
}
}
測(cè)試：正確
public static void main(String[] args) {
DiyHashMap<String, String> map = new DiyHashMap<>(2, 0.75f);
String key = "hello";
for(int i = 0; i < 10000; i++){
map.put(key + i, "world" + i);
}
for(int i = 0; i < 10000; i++){
String value = map.get(key + i);
if(!value.equals("world" + i)){
System.out.println("fail");
}
}
}
再來一個(gè)版本：
1屯伞、優(yōu)化了一下擴(kuò)容。
2豪直、因?yàn)?的n次方劣摇，需要比較麻煩的位運(yùn)算，所以除非復(fù)制hashmap的代碼弓乙，否則末融，手寫不出來。暇韧。
2的n次方寫不出勾习，那么取模運(yùn)算，也就優(yōu)化不了懈玻。
2的n次方寫不出來巧婶，就不能用高位，去推算擴(kuò)容后的位置，所以擴(kuò)容后也就只能鏈表倒置了艺栈。
3英岭、紅黑樹太復(fù)雜了，也不寫湿右。
public class DiyHashMapV2<K, V> {
private DiyHashMapV2.Node[] nodes;
private int size;
private Integer threshold;
private Float rate;
private Integer length;
public DiyHashMapV2(Integer length, Float rate) {
this.length = length;
this.rate = rate;
Float temp = length * rate;
this.threshold = temp.intValue();
}
private class Node {
private K key;
private V value;
private Node next;
public Node(K key, V value) {
this.key = key;
this.value = value;
}
}
public void put(K k, V v) {
if (nodes == null) {
nodes = new DiyHashMapV2.Node[length];
}
if (size >= threshold) {
// 擴(kuò)容
resize();
}
Node node = new Node(k, v);
int index = indexOfArray(k.hashCode());
if (nodes[index] == null) {
nodes[index] = node;
size++;
} else {
// 鏈表查找
Node n = nodes[index];
while (true) {
if (n.next == null) {
// 直接隊(duì)列尾放置
n.next = node;
size++;
break;
} else if (n.next.key.hashCode() == k.hashCode() && n.next.key.equals(k)) {
// 替換
n.next.value = v;
break;
} else {
// 往下遍歷
n = n.next;
}
}
}
}
// 就重寫了一下擴(kuò)容方法
public void resize() {
int newLength = length << 1;
this.length = newLength;
Float temp = length * rate;
this.threshold = temp.intValue();
Node[] oldNodes = nodes;
DiyHashMapV2.Node[] newNodes = new DiyHashMapV2.Node[newLength];
this.nodes = newNodes;
for (int i = 0; i < oldNodes.length; i++) {
Node oldNode = oldNodes[i];
while (true) {
if (oldNode != null) {
int newIndex = indexOfArray(oldNode.key.hashCode());
// 新數(shù)組的這個(gè)位置是否有值
if (null == newNodes[newIndex]) {
newNodes[newIndex] = oldNode;
oldNode = oldNode.next;
// 這里需要把以前的next指標(biāo)清空诅妹，否則，因?yàn)橐闳耍瑪U(kuò)容后吭狡，鏈表倒置了，會(huì)造成鏈表循環(huán)next丈莺，也就是鏈表的最后一個(gè)元素的next會(huì)指向鏈表的第一個(gè)元素
newNodes[newIndex].next = null;
} else {
// 直接放到頭部
Node tmp = oldNode.next;
Node t = newNodes[newIndex];
newNodes[newIndex] = oldNode;
oldNode.next = t;
oldNode = tmp;
}
} else {
break;
}
}
}
}
public int indexOfArray(int hashcode) {
int i = hashcode % length;
if(i < 0){
return 0 - i;
}
return i;
// return 1;
}
public V get(K k) {
int index = indexOfArray(k.hashCode());
Node node = nodes[index];
while (true) {
if (node == null) {
return null;
} else if (node.key.hashCode() == k.hashCode() && node.key.equals(k)) {
// 找到了
return node.value;
} else {
node = node.next;
}
}
}
}
測(cè)試一下性能：
測(cè)試結(jié)果其實(shí)性能差不多划煮。
測(cè)試的結(jié)果不是很精確，因?yàn)槊看味疾灰粯拥薅恚愦耍琧pu的波動(dòng)，分配的執(zhí)行時(shí)間有關(guān)牵现。
public static void main(String[] args) {
String key = "hello";
DiyHashMap<String, String> map = new DiyHashMap<>(16, 0.75f);
for (int i = 0; i < 5000000; i++) {
map.put(key + i, "world" + i);
}
long start = System.nanoTime();
DiyHashMap<String, String> map1 = new DiyHashMap<>(16, 0.75f);
for (int i = 0; i < 5000000; i++) {
map1.put(key + i, "world" + i);
}
/*
測(cè)試铐懊，能不能取到元素
for (int i = 0; i < 10000; i++) {
String value = map.get(key + i);
if (!value.equals("world" + i)) {
System.out.println("fail");
}
}*/
long end = System.nanoTime();
DiyHashMapV2<String, String> map2 = new DiyHashMapV2<>(16, 0.75f);
for (int i = 0; i < 5000000; i++) {
map2.put(key + i, "world" + i);
}
long end2 = System.nanoTime();
Map<String, String> map3 = new HashMap<>(16, 0.75f);
for (int i = 0; i < 5000000; i++) {
map3.put(key + i, "world" + i);
}
long end3 = System.nanoTime();
System.out.println(end - start);
System.out.println(end2 - end);
System.out.println(end3 - end2);
}
3128620097
5787549157
3656479197
