HashMap
内部用数组存储内部类Node包装的Key-Value,用Key的哈希值来计算数据在数组中的位置,如果遇到计算出来的位置已经有值,则以链表的方式在后面添加,当链表长度变大时,则将其转为红黑树
1 |
|
Object的hashcode采用native C实现,返回实例内存地址,String的默认实现如下:
1 |
|
HashMap中计算数组位置的方法如下:
1 |
|
另外,Object中equals的实现是判断两个Object指针是否指向了同一个内存地址, 同时注释中也建议如果覆盖该方法也同时覆盖hashCode方法,为了保证相等的对象也具有相同的哈希值。
1 |
|
一致性哈希算法
在分布式缓存系统中为了解决取模求分配机器在机器增减时带来的大量数据迁移问题,采用了一致性哈希算法。简单来说就是将哈希空间想象成0~$2^{32}$-1的环,将集群中的机器取一个哈希值$h_i$,对数据取哈希值,沿顺时针寻找,将其放在第一个遇到的$h_i$对应的机器上。同时为了避免机器数量较少时数据分布不均匀和机器宕机时其数据全部落在环上下一台机器上,引入了虚拟节点的概念,环上设置多个虚拟点,然后间隔的均匀的选取虚拟点将其映射到实际机器上。在实现上可以利用TreeMap的tailMap函数来取大于当前数据哈希值的最小$h_i$。
LinkedHashMap
LinkedHashMap是在HashMap的基础上,将数据用双向链表连接起来,数据插入时被放在链表的尾部,如果数据已经存在则将其取出更新再插入在链表尾部,数据读取时也将其取出放入链表的尾部。这天然就可以支持Least Recently Use缓存清除策略的实现。
ConcurrentHashMap
它在HashMap的基础上实现了多线程安全,在Java 1.7的版本中主要通过分段锁(ReentrantLock)数组来实现的,在Java 1.8中则利用CAS+Synchronized来实现, 相当于将分段细分到了数组中的每个元素。下面以put函数为例来看下它是如何实现的:
1 |
|
在transfer中进行数组扩容,分为创建新数组和从旧数组迁移数据到新数组,其中第二步是可以多线程并行完成,每个线程都将处理完的数组位置附上ForwardingNode代表已完成。