Java HashMap 与 HashSet

HashMap

• HashMap 是 Map 接口的实现类，允许使用 null 值 null 键，它不保证映射顺序，特别是不保证该顺序恒久不变，也非线程安全的

HashMap 内部结构

• HashMap 内部是一个"链表散列"的数据结构（是基于数组与引用），底层是一个数组，数组中的每一项又是一个链表 Entry 对象
• Entry 是一个静态类，包含了 key-value 键值对对象，还包含了一个 next 引用指向下一个 Entry 对象

HashMap 扩容

• 当 HashMap 内的元素越来越多时，hash 的冲突几率也会越来越高，因为数组的长度是固定的，为了提高效率就必须对数组进行扩容，但扩容十分消耗性能，因为原数组中的数据必须重新计算其在新数组中的位置，如果事先预知元素大小，那么预设个数就能提高性能
• 当 HashMap 中的元素个数超过 数组大小*loadFactor（加载因子）时就会进行扩容（默认数组容量为 16、加载因子为0.75）
• 加载因子越高代表对空间的利用更充分，但查询效率低
• 加载因子太小，数据太稀疏，浪费了空间资源

HashMap 的 put()、get() 方法简述

• put 方法
  • 当 put 元素时，会先根据 key 计算其 hashCode，决定该元素要存放在数组中哪个位置
  • 如果该数组位置上没有元素，则直接存放，如果已有元素，则存放在链头
  • 如果 key 已经存在，新的 value 就会替换旧的 value，并返回旧的 value，否则返回 null
• get 方法
  • 当 get 元素时，会先根据 key 计算 hash 值求的元素对应数组中的位置
  • 再通过 equals() 方法判断，从链表中取出 Entry

HashMap 用法

HashMap<String,Integer> hashMap = new HashMap<>();
hashMap.put("a",1);
hashMap.put("b",2);
hashMap.forEach((k,v)->{
    System.out.println(k);
    System.out.println(v);
});

HashSet

• HashSet 底层是基于 HashMap 实现的，因此它也非线程安全，也不能保证元素的插入顺序
• 当 put 元素时，如果元素不存在则添加，否则返回 false
• HashSet 跟 HashMap 一样存储着 <key,value> 结构的 Entry 对象，但 HashSet 中的 value 都是 PRESENT

HashSet 用法

HashSet<Integer> integers = new HashSet<>();
integers.add(1);
integers.add(2);
integers.forEach(i -> System.out.println(i));