Java 中的哈希表数据结构

哈希表数据结构

• HashMap集合：
• 在JDK8之后，如果单向链表中的元素超过8个，单向链表数据结构就会变成红黑树数据结构，当红黑树上的节点数量小于6时，会重新把红黑树变成单向链表数据结构。
• HashMap集合底层是哈希表/散列表的数据结构
• 哈希表是一个怎样的数据结构？
  哈希表是一个数组和单向链表的结合体
  数组：在查询方面效率很高
  单向链表：在随机增删方面效率很高
  • 哈希表将两种数据结构结合在一起，充分发挥他们各自的优点
    最主要掌握的是：
  • map.put(k,v)
  • v = map.get(k)
    这两个方法的实现原理。
  • 重点：通过讲解可以得出HashMap集合的Key，会先后调用两个方法 hashCode(),equals(),这两个方法都需要重写
  • HashMap集合的默认初始化容量是16，默认加载因子是0.75：这个默认加载因子是当HashMap集合底层数组容量达到75%的时候，数组开始扩容
    重点：HashMap集合初始化容量必须是2的倍数，这也是官方推荐
  • 这是因为达到散列均匀，为了提高HashMap集合的存取效率，所必须的。
  • hashcode()和 equals()方法可以直接使用IDEA工具直接生成，但是这两个方法需要同时生成。使用Alt + Ins来生成
    

HashMap集合允许key为null，但是null值只会有一个。Hashtable集合不允许key为null

Hashtable的初始化容量是11，默认加载因子是0.75。Hashtable扩容后是原容量的两倍加1