自定义简单实现hashmap
Hashmap基本结构讲解
哈希表(散列表)的基本结构就是“数组+链表”
其中的Entry[] table 就是HashMap的核心数组结构，我们也称之为“位桶数组”
Entry是什么，源码如下：
一个Entry对象存储了：
-
key：键对象 value：值对象
-
next:下一个节点
-
hash: 键对象的hash值
显然每一个Entry对象就是一个单向链表结构，我们使用图形表示一个Entry对象的典型示意：
然后，我们画出Entry[]数组的结构(这也是HashMap的结构)：
HashMap之所以能根据key直接拿到value，原因是它内部通过空间换时间的方法，用一个大数组存储所有value，并根据key直接计算出value应该存储在哪个索引
如果添加超过16个key-value到HashMap，数组不够用了怎么办？
添加超过一定数量的key-value时，HashMap会在内部自动扩容，每次扩容一倍，即长度为16的数组扩展为长度32，相应地，需要重新确定hashCode()计算的索引位置。
例如，对长度为32的数组计算hashCode()对应的索引，计算方式要改为：
int index = key.hashCode() & 0x1f; // 0x1f = 31
由于扩容会导致重新分布已有的key-value，所以，频繁扩容对HashMap的性能影响很大。如果我们确定要使用一个容量为10000个key-value的HashMap，更好的方式是创建HashMap时就指定容量：
Map<String, Integer> map = new HashMap<>(10000)
虽然指定容量是10000，但HashMap内部的数组长度总是2n，因此，实际数组长度被初始化为比10000大的16384（214）。
简单实现
- 定义节点
package TestList.TestMap;
public class Node2<K,V> {
int hash;
K key;
V value;
Node2 next;
}
- 具体实现（主要是put方法）
package TestList.TestMap;
/**
* 自定义Hashmap
* 采用数组+链表形式存储元素
* hash值对应在哈希表（散列表）的存储位置，通过hashcode计算出hash，用除留余数法，尽可能均匀分布
*/
public class HashMap01<K,V> {
Node2[] table;//位桶数组,bucket array;java中数组是对象，
int size;//存放的键值对的个数
public HashMap01(){
table = new Node2[16];//长度一般定义为2的整数幂
}
/**遍历bucket数组*/
public void put(K key,V value){
//定义了新节点对象
Node2 newNode = new Node2();
newNode.hash = myHash(key.hashCode(),table.length);//小心这里，一开始写成了myHash(key,hashcode(),table.length)
newNode.key = key;
newNode.value = value;
// newNode.next = null;
Node2 temp = table[newNode.hash];
if (temp == null) {
/**此处数组元素为空，直接将新节点放进去*/
table[newNode.hash] = newNode;//不可写成 temp = newNode
size++;
}else{
/**此处元素不为空，则遍历对应链表*/
while (temp != null) {
if (temp.key.equals(key)){//若键值重复，覆盖
keyRepeat = true;
System.out.println("键重复了");
temp.value = value;//覆盖value即可，其他的（hash,key,next）保持不变
break;//发现键值相同，后面不再遍历
}
else {//key不重复，遍历下一个
if(temp.next == null){
temp.next = newNode;//遍历到表尾
size++;
}
temp = temp.next;//遍历之后iterLast成为最后一个节点
}
}
}
}
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.key.equals(key)){
value = ((V) temp.value);//如果相等，说明找到了键值对，返回相应的value即可
break;//千万别忘记
}else{
temp = temp.next;
}
}
}
return value;
}
/**
* 自定义散列函数，用除留余数法
* 当数组长度是2的整数幂时，(v & (length - 1))与(v % length)结果相同
* 例如23 % 16 = 7；0x17 & 0x0F = 7
*/
public static int myHash(int v,int length){
System.out.println("hash in Myhash:" + (v & (length - 1)));//直接位运算，效率高
// System.out.println("hash in Myhash:" + (v % length));//除留余数法
return v&(length - 1);
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder("{");
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();
}
public static void main(String[] args) {
HashMap01<Integer,String> map = new HashMap01<>();
map.put(21, "qin");
map.put(37, "qi");
map.put(53, "q");
map.put(53, "qq");
System.out.println(map);
System.out.println(map.get(37));
}
}
结果如下
hash in Myhash:5
hash in Myhash:5
hash in Myhash:5
hash in Myhash:5
键重复了
{21:qin;37:qi;53:qq}
hash in Myhash:5
qi
除此以外还应注意
if (temp.next == null) {
temp.next = newNode;
break;//别忘记跳出循环
}
temp = temp.next;
顺序也不能颠倒，不能将temp = temp.next一句放到 if 判断前面，否则也会报错
Exception in thread "main" java.lang.NullPointerException