HashMap源码分析
1.底层数据结构
HashMap的底层数据结构是和哈希表。
数组在查询方面效率很高，随机增删效率很低。单向链表在随机增删方面效率很高，在查询方面效率很低。
哈希表是数组和单向链表的结合体，将以上优势融合在一起。
2.Node结点
HashMap实际上就是Node类型的一个数组，Node是一个静态内部类，Node结点由哈希值、key、value和指向下一个结点的内存地址这四部分组成。
哈希值是HashCode()方法的执行结果，哈希值通过哈希函数（哈希算法）转换成数组的下标。
源码如下：
//静态内部类，类型为HashMap.Node static class Node<K,V> implements Map.Entry<K,V> { final int hash; final K key; V value; Node<K,V> next; //Node节点结构 Node(int hash, K key, V value, Node<K,V> next) { this.hash = hash; //哈希值 this.key = key; this.value = value; this.next = next; } public final K getKey() { return key; } public final V getValue() { return value; } public final String toString() { return key + "=" + value; } public final int hashCode() { return Objects.hashCode(key) ^ Objects.hashCode(value); } public final V setValue(V newValue) { V oldValue = value; value = newValue; return oldValue; } public final boolean equals(Object o) { if (o == this) return true; if (o instanceof Map.Entry) { Map.Entry<?,?> e = (Map.Entry<?,?>)o; if (Objects.equals(key, e.getKey()) && Objects.equals(value, e.getValue())) return true; } return false; } }
3. 哈希表结构图
4.无序不可重复
前面写的无序不可重复此时可以解释。
无序：HashMap底层是哈希表，一个元素存进来之后不一定会存到哪个单链表上，因此取出的时候也不一定会以什么顺序取出去。
不可重复：HashMap在存入元素时，会将新存入的k与链表中的每一个key进行equals比对，如果重复则覆盖原先的value值。
5.初始化
HashMap集合初始化的数组容量是16，默认加载因子是0.75。
默认加载因子是当HashMap底层数组的容量占了75%以上，数组会自动扩容。
重点**：HashMap集合初始化容量必须是2的倍数，这也是官方推荐的，这是为了达到散列均匀，提高HashMap集合的存取效率。**
源码如下：
/** * Constructs an empty {@code HashMap} with the default initial capacity (16) and the default load factor (0.75). */ public HashMap() { this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted }
6.自动扩容
HashMap集合底层的数组扩容，新容量是旧容量的二倍，新容量为旧容量左移一位，源码如下：
7.key为null
HashMap集合的key是可以为null的，并且重复存储key为null时会覆盖掉原先的value，也可也根据key=null取到value，以下为测试代码和结果：
public static void main(String[] args) { Map map=new HashMap(); map.put(null,null); System.out.println(map.size());//1 System.out.println(map.get(null));//null map.put(null,110); System.out.println(map.get(null));//110 }
四、hashCode和equals
HahsMap集合使用put方法时，底层会调用hashCode方法将key转换为hash值，然后根据哈希函数/哈希算法将哈希值转换为数组下标，若此下标的数组没有元素，则直接添加，若此下标的数组有链表，则将key与链表中每个节点的key进行equals比对，若都返回false，则将元素添加在链表末尾，若返回true，则将此节点的value覆盖。
1.hashCode方法
hashCode方法会返回hash值，若一个类未重写hashCode方法，则会使hash值始终不一样，调用的是Object类中的hashCode方法，返回的是内存地址。**重写hashCode方法之后，会根据类的属性进行返回hash值，两个key和value部分内容相同的对象返回的hash值是一样的，key和value部分有任一不相同的对象，返回的hash值是不一样的。**测试代码及结果如下：
l 未重写hashCode方法
User类
class User{ private int id; private String name; public User() { } public User(int id, String name) { this.id = id; this.name = name; } public int getId() { return id; } public void setId(int id) { this.id = id; } public String getName() { return name; } public void setName(String name) { this.name = name; } @Override public String toString() { return "User{" + "id=" + id + ", name='" + name + '\'' + '}'; } @Override public boolean equals(Object o) { if (this == o) return true; if (o == null || getClass() != o.getClass()) return false; User user = (User) o; return id == user.id && Objects.equals(name, user.name); } } 测试： public static void main(String[] args) { Map<User,Integer> map=new HashMap<>(); User u1=new User(1,"zhangsan"); User u2=new User(1,"zhangsan"); System.out.println("u1的hash值="+u1.hashCode()); System.out.println("u2的hash值="+u2.hashCode()); map.put(u1,2); map.put(u2,2); System.out.println(); Set<Map.Entry<User, Integer>> entries = map.entrySet(); for (Map.Entry<User, Integer> entry : entries) { System.out.println(entry.getKey()+"="+entry.getValue()); } } :
结果：
