TreeMap
2022-08-27 15:02:05 6 举报AI智能生成
用于准备面试，记录概要的特性，方便记忆
作者其他创作
大纲/内容
源码
成员变量comparator：如果不提供Comparator，
那么要求key实现Comparable接口，否则put()会抛异常
那么要求key实现Comparable接口，否则put()会抛异常
排序的优先级：有限Comparator，然后Comparable
Entry类型的root指针，指向根节点
TreeMap是一颗二叉树，整个TreeMap是按照key排序存储的
可以实现一致性hash
面试问题
如何使用TreeMap实现一致性hash
由来
MemCache写缓存的流程
应用程序APP通过API接口问MemCache
MemCache的路由算法告诉要去哪台服务器节点写缓存
分析
常规路由算法是余数hash，公式 = hash值 % 服务器节点个数
如果不考虑服务器集群的伸缩性，余数hash没问题
如果给集群扩容，那么 “服务器节点个数” 就会改变，得到的结果也会改变
那么会造成读缓存时绝大部分缓存不命中，并且原有的缓存也一直占据内存空间导致在别的节点写缓存是多余的，浪费资源
解决
在访问量低谷时期（比如深夜），技术团队加班、扩容
模拟用户请求预热热点数据到缓存服务器节点上
解决
构建一个长度2^32的整数环。
根据服务器节点名称的hash值将节点放在这个环上
根据需要缓存的数据的key的hash值，在环上顺时针查询距离这个key的hash值最近的服务器节点
完成key到服务器节点的映射查找
考虑到服务器节点可能分布不均匀，可以在分配服务器节点时做一定数量的虚拟节点。避免大部分数据命中同一个节点
0 条评论
下一页
