java入门必看--HashMap底层原理和手写HashMap
3.1 HashMap的原理
• 底层结构是哈希表，采用了顺序表+链表结合结构；同一个链表的上所有元素的存储地址都是相同的，是发生冲突的元素

• 链表上每个节点的就是一个Entry，字段包括四部分

问：同一个链表上节点的哈希码相同吗？？哈希码可能不相同，存储地址相同。
• 哈希表的优点
• 添加快、查询快（通过计算得到存储位置，不是通过比较）
• 无序
• （key）唯一
• 关键参数
• 默认主数组长度16；
• 默认装填因子0.75。
• 每次主数组扩容为原来的2倍
• JDK8，当链表长度大于8，链表变成红黑树

• 第一步计算哈希码，不仅调用了hashCode()，有进行了多次散列。目的在于key不同，哈希码尽量不同，减少冲突
final int hash(Object k) { int h = 0; h ^= k.hashCode(); h ^= (h >>> 20) ^ (h >>> 12); return h ^ (h >>> 7) ^ (h >>> 4); }
• 细节：发生冲突，经过比较不存在相同key的元素，要添加一个新的节点。不是加到链表最后，而是添加到链表最前


3.2定义Map接口
【示例11】 定义Map接口
public interface Map { //定义方法 public void put(Object key,Object value); public Object get(Object key); public int size(); public boolean isEmpty(); //定义内部接口 interface Entry{ public Object getKey(); public Object getValue(); } }
3.3手写HashMap
【示例12】 手写HashMap
public class HashMap implements Map { public Entry[] table;//指向哈希表的数组引用 int size;//键值对的数量 public HashMap() { table = new Entry[11];//哈希表主数组默认长度16 } public void put(Object key, Object value) { //计算哈希码 int hash = key.hashCode(); //根据哈希码计算存储位置 int index = hash % table.length; //存入指定位置 if (table[index] == null) {//如果该位置没有元素，增加一个节点 table[index] = new Entry(hash, key, value); size++; } else {//如果有元素，进行逐个比较 Entry entry = table[index]; //Entry previousEntry = null; while (entry != null) { //如果找到了相同的key if (entry.getKey().equals(key)) { //新的value替代旧的value entry.value = value; return; } //previousEntry = entry; entry = entry.next; } //循环结束，表明也没有相同的key，在链表最后添加一个节点 //previousEntry.next = new Entry(hash, key, value); //循环结束，表明也没有相同的key，在链表最前边添加一个节点 Entry firstEntry = table[index]; table[index] = new Entry(hash, key, value,firstEntry); size++; } } public Object get(Object key) { //计算哈希码 int hash = key.hashCode(); //根据哈希码计算存储位置 int index = hash % table.length; //查找对应的Entry Entry entry = null; if (table[index] != null) { Entry currentEntry = table[index]; while (currentEntry != null) { if (currentEntry.getKey().equals(key)) { entry = currentEntry; break; } currentEntry = currentEntry.next; } } return entry == null ? null : entry.getValue(); } public String toString() { StringBuilder builder = new StringBuilder("{"); for(int i=0;i<table.length;i++){ if(table[i] != null){ Entry entry = table[i]; while(entry != null){ builder.append(entry.getKey()+"="+entry.getValue()+","); entry = entry.next; } } } if(builder.length()!=1){ builder.deleteCharAt(builder.length()-1); } builder.append("}"); return builder.toString(); } public int size() { return size; public boolean isEmpty() { return size == 0; } class Entry implements Map.Entry { private int hash;//哈希码 private Object key;//键 private Object value;//值 private Entry next;//指向下一个节点的指针 public Entry() { } public Entry(int hash, Object key, Object value) { this.hash = hash; this.key = key; this.value = value; } public Entry(int hash, Object key, Object value, Entry next) { this.hash = hash; this.key = key; this.value = value; this.next = next; } public Object getKey() { return key; } public Object getValue() { return value; } public String toString() { if (next != null) { return "{" + key + ":" + value + "-" + hash + " " + next + "}"; } else { return "{" + key + ":" + value + "-" + hash + "}"; } } } }
1.4测试HashMap
【示例13】 测试HashMap
public class TestHashMap { public static void main(String[] args) { java.util.HashMap map2; HashMap map = new HashMap(); map.put(23,"China"); map.put(36,"Japan"); map.put(48,"America"); map.put(86,"the United States"); map.put(67,"France"); map.put(23,"Italian"); map.put(47,"England"); System.out.println(map.size()); System.out.println(Arrays.toString(map.table)); System.out.println(map); } }