网站开发公司+重庆,wordpress自定义搜索界面,社团建设制作网站费用会计科目,软件开发面试问题大全及答案大全Java之HashMap的底层实现 摘要HashMap的底层原理哈希值转换为数组下标节点初始化put(Object key, Object value)重写toString()get(Object key)增加泛化remove(K key) 摘要
本博客主要讲述了Java的HashMap的底层实现
HashMap的底层原理
底层原理#xff1a;数组链表 过程… Java之HashMap的底层实现 摘要HashMap的底层原理哈希值转换为数组下标节点初始化put(Object key, Object value)重写toString()get(Object key)增加泛化remove(K key) 摘要
本博客主要讲述了Java的HashMap的底层实现
HashMap的底层原理
底层原理数组链表 过程总结每一个Object的有一个哈希值通过hashCode()函数获取哈希值再通过自定义的hash()函数得到一个值也就是数组的下标。数组中的每个元素都是一个链表或为空。
哈希值转换为数组下标 //这就是hash函数val就是key的哈希值即val key.hashCode()
//length 必须是2的整数幂
private int hash(int val, int length){return val (length - 1);}节点
定义链表中的节点
public class Node2 {int hash;//hash对应数组下标Object key;Object value;Node2 next;
}初始化
//数组元素的类型为Node2
Node2[] table;
int size;public SxtHashMap02() {table new Node2[16];
}put(Object key, Object value)
public void put(Object key, Object value){Node2 newNode new Node2();newNode.hash hash(key.hashCode(),table.length);newNode.key key;newNode.value value;newNode.next null;Node2 last null;//这个学习一下记录最后一个节点int index hash(key.hashCode(),table.length);if(table[index] null){table[index] newNode;size ;}else{Node2 tmp table[index];while(tmp ! null){if(key.equals(tmp.key)){System.out.println(key重复了);tmp.value value;return;}else {last tmp;tmp tmp.next;}}last.next newNode;size ;//size的增加与减少不要忘记}}重写toString()
public String toString() {StringBuilder sb new StringBuilder();sb.append([);for(int i 0; i table.length; i ){Node2 temp table[i];while(temp ! null){sb.append(temp.key : temp.value ,);temp temp.next;}}//这个套路学一下将最后改为]sb.setCharAt(sb.length() - 1,]);return sb.toString();
} 这个toString()有什么用呢在使用system.out.println()打印的时候就会用到toString()。
get(Object key)
//根据Map的底层原理就十分简单
public Object get(Object key){int hashCode key.hashCode();int hash hash(hashCode,table.length);Node2 temp table[hash];while(temp ! null){if(temp.key.equals(key)) return temp.value;temp temp.next;}return null;
}增加泛化
public class Node3K,V {int hash;K key;V value;Node3 next;
}public class SxtHashMap03K,V {Node3[] table;int size;public SxtHashMap03() {table new Node3[16];}public V get(K key){int hashCode key.hashCode();int hash hash(hashCode,table.length);V value null;Node3 temp table[hash];while(temp ! null){if(temp.key.equals(key)){value (V)temp.value;}temp temp.next;}return value;}public void put(K key, V value){Node3 newNode new Node3();newNode.hash hash(key.hashCode(),table.length);newNode.key key;newNode.value value;newNode.next null;Node3 last null;int index hash(key.hashCode(),table.length);if(table[index] null){table[index] newNode;size ;}else{Node3 tmp table[index];while(tmp ! null){if(key.equals(tmp.key)){System.out.println(key重复了);tmp.value value;return;}else {last tmp;tmp tmp.next;}}last.next newNode;size ;}}
}remove(K key) public void remove(K key){int index hash(key.hashCode(), table.length);Node3 temp table[index];if(temp null) return;if(temp.key.equals(key)){table[index] temp.next;size --;return;}Node3 last null;while(temp ! null){if(temp.key.equals(key)){last.next temp.next;size --;return;}last temp;temp temp.next;}
}参考: 手工实现HashMap
