equals()/hashcode()/hash表/hashmap/linkedhashmap/和变量在内存中的存储关系之间的联系

首先在讲解三者之间的关系的时候我们会先进行hash表的讲解 以问题的方法逐步解答首先讲解一下什么是hash表然后逐步进行讲解1.hash表hash表的数据结构jdk8之前hash表是由 数组 链表jdk8之后数组 链表 红黑树哈希表HashMap结构 ┌─────────────────────────────────────────────────────────┐ │ NodeK,V[] table │ │ ┌─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┐ │ │ │ 0 │ 1 │ 2 │ 3 │ 4 │ 5 │ 6 │ 7 │ ... │ ← 数组默认长度16 │ └──┬──┴──┬──┴──┬──┴──┬──┴──┬──┴──┬──┴──┬──┴──┬──┘ │ │ │ │ │ │ │ │ │ │ │ ▼ ▼ ▼ ▼ ▼ ▼ ▼ │ │ null 链表 null 红黑树 null 链表 null │ │ │ │ │ │ │ ▼ ▼ ▼ │ │ Node1 TreeNode Node1 │ │ Node2 / \ Node2 │ │ Node3 Node Node Node3 │ │ 红黑节点 │ └─────────────────────────────────────────────────────────┘hash表的存储概述1.初始话操作hash表采用的是懒加载机制初始化容量默认是16的数组但是是在第一次添加元素的时候才进行初始的2.扩容操作哈希表有一个默认的加载因子(扩容临界值)0.75F,代表的是数组存储达到百分之75的时候扩容扩容是原来的2倍3.转化为红黑树可以自动平衡 提高查询效率当链表的长度为8并且数组的容量大于64的时候才能进行红黑树的转化必须同时满足两个条件如果在同一个数组索引下面删除链表元素当链表长度小于等于6时红黑数会自动转变为链表4.hash表中数组的索引是怎么进行计算的在新版本的jdk中计算哈希值的时候添加了一个扰动函数hash(Object key)这个扰动函数就是下面这个这个扰动函数返回的是一个经过扰动处理的hash值让高16位也参与索引计算目的是为了减少哈希冲突对原本的hash值进行优化经过扰动函数之后进行索引的计算下面代码是计算下标的主要代码(n - 1) hash 这个n是代表当前数组长度当n是 2 的幂时(n - 1) hash等价于hash % n但位运算更快这样之后就计算出了数组的下标key 张三 │ ▼ key.hashCode() 0x12345678 (假设) │ ▼ hash 0x12345678 ^ (0x12345678 16) 0x12345678 ^ 0x00001234 0x1234444C │ ▼ n 16 (数组长度) n-1 15 (二进制: 1111) │ ▼ index (16-1) 0x1234444C 15 0x1234444C 取低4位 12 (假设) │ ▼ table[12] 位置存储该节点5.那么有了数组下标之后为什么不能直接通过索引进行获取呢首先是上面看到数组的索引计算是 数组长度-1 与上 计算出的hash值因为数组长度会进行扩容进行扩容之后数组的长度会变所以相应的数组索引也是会进行改变的导致扩容后同一索引的内容会不同。即扩容后失效。其次就是一个位置存储一个key但是可能存储多个value这个就不不知道具体获取哪个所以没有提供使用索引获取。但是我个人认为这个并不是主要原因主要原因还是上面的扩容失效。6.为什么hashmap和linkedhashmap存储顺序存在差异呢即为什么hashmap存储无序linkedhashmap存储有序呢首先先看hashmap底层的结构是hash表HashMap 数组 链表/红黑树 数组索引: 0 1 2 3 4 5 6 7 ┌────┬────┬────┬────┬────┬────┬────┬────┐ │ │ ● │ │ ● │ │ │ ● │ │ └────┴─┬──┴────┴─┬──┴────┴────┴─┬──┴────┘ │ │ │ ▼ ▼ ▼ 链表/红黑树 链表/红黑树 链表/红黑树遍历顺序是按数组索引 0→1→2→3... 依次遍历每个桶桶内再按链表/红黑树顺序遍历但是索引的建立是和hashkey决定的和插入顺序无关 所以是无序的再看linkedhashmap底层结构是hash表和双向链表LinkedHashMap 数组 链表/红黑树 双向链表维护顺序 ┌─────────────────────────────────────────────────────────┐ │ 双向链表维护顺序 │ │ 头节点 ←→ 张三 ←→ 李四 ←→ 王五 ←→ 赵六 ←→ 尾节点 │ └─────────────────────────────────────────────────────────┘ │ ▼ ┌─────────────────────────────────────────────────────────┐ │ 哈希表快速查找 │ │ ┌────┬────┬────┬────┬────┬────┬────┬────┐ │ │ │ │ ● │ │ ● │ │ ● │ │ │ │ │ └────┴─┬──┴────┴─┬──┴────┴─┬──┴────┴────┘ │ │ │ │ │ │ │ ▼ ▼ ▼ │ │ 李四 赵六 张三→王五 │ └─────────────────────────────────────────────────────────┘插入时自动维护双向链表记录插入顺序遍历时走双向链表而不是哈希表7.hash表的存储过程存储自定义对象的时候需要重写hashCode和equals方法先比较hash值 不一样存储一样的话 再比较内容内容一样不存储内容不一样存储注意哈希值不一样,内容肯定不一样哈希值一样,内容也有可能不一样2.为什么重写完equals()方法之后一定要重写hashCode()方法equals是常见的方法在没有重写之前是继承Objec类的equals方法object类的方法比较的是地址值而不是内容的比较。public boolean equals(Object obj) { return (this obj); }重写之后比较的是内容。但是重写完equals之后还是需要重写hashCode方法因为重写equals之后内容相同但hashCode有可能是不同的例如下面的例子 没有重写hashCodepublic class Student { private String name; private int age; //在这里先进行赋值操作 public Student() { this.name dill; this.age 11; } Override public boolean equals(Object o) { if (this o) return true; if (o null || getClass() ! o.getClass()) return false; Student student (Student) o; return age student.age Objects.equals(name, student.name); } Override public String toString() { return Student{ name name \ , age age }; } } Student s01 new Student(); Student s02 new Student(); HashMapStudent, String m01 new HashMap(); m01.put(s01,01); m01.put(s02,02); System.out.println(m01); //{Student{namedill, age11}02, Student{namedill, age11}01}结果出现了key的内容相同重复存储的问题。Object的hashCode()方法hash的s01和s02两个对象整个的值,Override public int hashCode() { return Objects.hash(name, age); }重写之后的hashCode()方法hash的是对象中的属性,所以hashmap进行存储的话需要重写hashCode方法