HashMap是由数组和链表组成，数组存放链表头。存放数据需要键值对（key和value），根据key并通过hashCode()方法生成哈希码，再通过使用myHash()方法生成哈希值。通过哈希值找到数组位置（table[hash]）对应的链表。如果存在key，那么覆盖value，如果不存在，则建立新节点放入链表尾端。
数组长度一般对定义为2的整数幂。
myHash()方法会有两种方式:（1）hashCode & (length - 1)，这种方式效率较高，但是必须要求数组长度必须是2的整数幂。（2）hashCode%length，这种效率较低。一般会采用第一种方式计算哈希值。
package Conllection; /** * HashMap链表节点 * @author zhaoy * */ public class Node1 { int hash; Object K; Object V; Node1 next; public Node1() { } } package Conllection; /** * HashMap 底层简单实现 * * @author zhaoy * */ public class HashMap1<K,V> { Node1[] table;// 位桶数组 int size;// 键值对的数量 public HashMap1() { table = new Node1[16];// 长度需要是2的整数幂 } /** * 添加节点 * * @param key * @param value */ public void put(K key, V value) { Node1 newNode = new Node1(); newNode.hash = myHash(key.hashCode(), table.length); newNode.K = key; newNode.V = value; newNode.next = null; Node1 temp = table[newNode.hash];// table数组的第一个节点 Node1 lastNode = null;// 记录最后一个节点 if (temp == null) {// 数组位置节点为空 table[newNode.hash] = newNode;// 把新节点放入数组中 size++; } else { boolean flag = false;// 用于判断数组链表中有没有重复的key while (temp != null) { if (temp.K == newNode.K) {// 用重复的key temp.V = newNode.V; flag = true; break; } else { lastNode = temp; temp = temp.next; } } if (!flag) { lastNode.next = newNode; size++; } } } /** * 根据Key计算出哈希值，遍历链表找到value * @param key * @return */ public Object get(K key) { int hash = myHash(key.hashCode(),table.length); Node1 temp = table[hash]; while(temp!=null) { if(temp.K==key){ break; }else { temp=temp.next; } } return temp.V; } /** * 移除节点方法 * @param key */ public void remove(K key) { int hash = myHash(key.hashCode(), table.length); Node1 previous = table[hash]; Node1 temp=table[hash]; while(temp!=null) { if(temp.K==key) { break; }else { previous=temp; temp=temp.next; } } if(temp==null) { throw new RuntimeException("key不存在："+key); } if(temp==table[hash]) {//删头 table[hash]=temp.next; temp.next=null; }else if(temp.next!=null){//删中间 previous.next=temp.next; temp.next=null; }else {//删尾 previous.next=null; } size--; } /** * 根据哈希码和数组长度计算哈希值 * * @param hashCode * @param length * @return */ public int myHash(int hashCode, int length) { return hashCode & (length - 1);// 也可以使用hashCode%length,与运算效率更高 } @Override public String toString() { StringBuilder sb = new StringBuilder(); sb.append('['); for(int i=0;i<table.length;i++) { Node1 temp = table[i]; while(temp!=null) { sb.append(temp.K+"="+temp.V+","); temp=temp.next; } } sb.setCharAt(sb.length()-1, ']'); return sb.toString(); } /** * 主方法 * @param args */ public static void main(String[] args) { HashMap1<Integer,String> map= new HashMap1<>(); for(int i=0;i<50;i++) { map.put(i, i+i+""); } System.out.println(map);//4、20、36、52、68, map.remove(36); System.out.println(map);//4、20、36、52、68, } }
