1. 哈希

2. 哈希值

哈希值(哈希码值):是JDK根据对象的地址或者属性值,算出来的int类型的整数

object类中有一个方法可以获取对象的哈希值:

  1. Student s1 =new Student();
  2. int hash = s1.hashCode();
  3. System.out.println(hash);

我们可以通过重写hashCode方法,通过对象的属性值来生成hashcode

  1. @Override
  2. public int hashCode() {
  3.     int result = name != null ? name.hashCode() : 0;
  4.     result = 31 * result + age;
  5.     // 如果对象的值全部一致则hashcode也一致
  6.     return result;
  7. }

3. 哈希表

JDK8之前,底层采用 数组+链表 实现

JDK8以后,底层进行优化. 由 数组+链表+红黑树 实现.

4. HashSet集合

特点:

  • 底层数据结构是哈希表
  • 不能保证存储和取出顺序完全一致
  • 没有索引,不能使用普通for循环遍历

4.1. 原理

1.7版本原理

底层为哈希表 用数组+链表实现

  1. 创建一个默认长度16,默认加载因 0.75 的数组,数组名为table

    • 加载因:当数组存了160.75=12个元素时,数组会扩容为原先的*两倍
  2. 根据元素的哈希值跟数组的长度计算出应存入的位置
  3. 判断当前位置是否为null,如果是null直接存入
  4. 如果不为null,则代表已有元素,则调用equals方法比较属性值
  5. 如不一致,则存入数组,老元素挂在新元素下面(链表)

28. 哈希 - 图1

1.8版本 原理

底层结构为:哈希表 底层为数组、链表和红黑树的结合体

1.8版本优化了,当存放位置一致时,链表过长 需要对链表每个元素进行比较 当链表长度过长效率不太理想

所以在链表中添加红黑树来进行优化, 当链表长度为8时,(> 8)再添加会自动转成为红黑树

28. 哈希 - 图2

流程图

28. 哈希 - 图3

5. Map 集合

Map中 key value 为一对,必须存储为键值对

Map中的put方法,如果此key已经有值,则会替换此key中值,并返回旧值

5.1. 遍历map

5.1.1. keySet

通过keySet()获取所有key

  1. Set<String> strings = map.keySet();
  2. for (String string : strings) {
  3.     System.out.println(map.get(string));
  4. }

5.1.2. entrySet

通过entrySet获取所有键值对

  1. Set<Map.Entry<String, String>> entries = map.entrySet();
  2. for (Map.Entry<String, String> entry : entries) {
  3.     System.out.println(entry.getValue());
  4.     System.out.println(entry.getKey());
  5. }

5.1.3. forEach

  1. map.forEach((String key, String value) -> {
  2.     System.out.println(key+"  "+value);
  3. });

5.2. HashSet 原理

与HashSet一致

5.3. TreeMap 原理

与TreeSet 差不多

节点存储的为键值对,并且只对键进排序,值不影响