1. 数组

2. 链表

3. Hash表

3.1. HashMap

  • 数据结构

image.png

3.2. LinkedHashMap

  • 数据结构

image.png

3.3. TreeMap

3.6. JDK中解决Hash冲突的方式

3.6.1. 链地址法

  • 链地址法其实就是对Key通过哈希之后落在同一个地址上的值，做一个链表。

  • HashMap就是使用这种方式解决Hash冲突的

    3.6.2. 开放式寻址

  • 当需要存储值时，对Key哈希之后，发现这个地址已经有值了，这时该怎么办？不能放在这个地址，不然之前的映射会被覆盖。这时对计算出来的地址进行一个探测再哈希，比如往后移动一个地址，如果没人占用，就用这个地址。

  • ThreadLocal就是用这种方式解决冲突的
    • ThreadLocal特殊的设计
      • 数组长度不会太长
      • 定时清理无用key，减少冲突的概率
      • 通过一些特殊的机制来使得key的hash值尽量在数组中均匀分布。参见神奇的数字0x61c88647

        4. 队列

        5. 树