一, HashMap
1, 基于哈希表的 Map 接口的实现. 此实现提供所有可选的映射操作, 并允许使用 null 值和 null 键.(除了非同步和允许使用 null 之外, HashMap 类与 Hashtable 大致相同.)此类不保证映射的顺序, 特别是它不保证该顺序恒久不变.
2,HashMap 的实例有两个参数影响其性能: 初始容量 和加载因子. 容量是哈希表中桶的数量, 初始容量只是哈希表在创建时的容量. 加载因子是哈希表在其容量自动增加之前可以达到多满的一种尺度. 当哈希表中的条目数超出了加载因子与当前容量的乘积时, 则要对该哈希表进行 rehash 操作(即重建内部数据结构), 从而哈希表将具有大约两倍的桶数.
按照 key 关键字的哈希值和 buckets 数组的长度取模查找桶的位置, 如果 key 的哈希值相同, Hash 冲突 (也就是指向了同一个桶) 则每次新添加的作为头节点, 而最先添加的在表尾.
image
HashMap 中的桶的个数就是下图中的 0- n 的数组的长度, 存储第一个 entry 的位置叫'桶(bucket)'而桶中只能存一个值也就是链表的头节点, 链表的每个节点就是添加的一个值(HashMap 内部类 Entry 的实例 Entry 有哪些属性之后在详说), 也可以这样理解, 一个 entry 类型的存储链表的数组. 数组的索引位置就是一个个桶的索引地址.
image
从上图我们可以发现哈希表是由数组 + 链表组成的, 一个长度为 16 的数组中, 每个元素存储的是一个链表的头结点. 那么这些元素是按照什么样的规则存储到数组中呢. 一般情况是通过 hash(key)%len 获得, 也就是元素的 key 的哈希值对数组长度取模得到. 比如上述哈希表中, 12%16=12,28%16=12,108%16=12,140%16=12. 所以 12,28,108 以及 140 都存储在数组下标为 12 的位置.
HashMap 简单总结:
1,HashMap 是链式数组 (存储链表的数组) 实现查询速度可以, 而且能快速的获取 key 对应的 value;
2, 查询速度的影响因素有 容量和负载因子, 容量大负载因子小查询速度快但浪费空间, 反之则相反;
3, 数组的 index 值是 (key 关键字, hashcode 为 key 的哈希值, len 数组的大小):hashcode%len 的值来确定, 如果容量大负载因子小则 index 相同(index 相同也就是指向了同一个桶) 的概率小, 链表长度小则查询速度快, 反之 index 相同的概率大链表比较长查询速度慢.
4, 对于 HashMap 以及其子类来说, 他们是采用 hash 算法来决定集合中元素的存储位置, 当初始化 HashMap 的时候系统会创建一个长度为 capacity 的 Entry 数组, 这个数组里可以存储元素的位置称为桶(bucket), 每一个桶都有其指定索引, 系统可以根据索引快速访问该桶中存储的元素.
5, 无论何时 HashMap 中的每个桶都只存储一个元素 (Entry 对象). 由于 Entry 对象可以包含一个引用变量用于指向下一个 Entry, 因此可能出现 HashMap 的桶(bucket) 中只有一个 Entry, 但这个 Entry 指向另一个 Entry 这样就形成了一个 Entry 链.
6, 通过上面的源码发现 HashMap 在底层将 key_value 对当成一个整体进行处理 (Entry 对象) 这个整体就是一个 Entry 对象, 当系统决定存储 HashMap 中的 key_value 对时, 完全没有考虑 Entry 中的 value, 而仅仅是根据 key 的 hash 值来决定每个 Entry 的存储位置.
JDK1.8 中使用一个 Node 数组来存储数据, 但这个 Node 可能是链表结构, 也可能是红黑树结构如果插入的 key 的 hashcode 相同, 那么这些 key 也会被定位到 Node 数组的同一个格子里.
如果同一个格子里的 key 不超过 8 个, 使用链表结构存储. 如果超过了 8 个, 那么会调用 treeifyBin 函数, 将链表转换为红黑树. 那么即使 hashcode 完全相同, 由于红黑树的特点, 查找某个特定元素, 也只需要 O(log n)的开销
也就是说 put/get 的操作的时间复杂度最差只有 O(log n).
需要注意: key 的对象, 必须正确的实现了 Compare 接口
二, TreeMap
红黑树是一种近似平衡的二叉查找树, 它能够确保任何一个节点的左右子树的高度差不会超过二者中较低那个的一陪. 具体来说, 红黑树是满足如下条件的二叉查找树(binary search tree):
每个节点要么是红色, 要么是黑色.
根节点必须是黑色
红色节点不能连续(也即是, 红色节点的孩子和父亲都不能是红色).
对于每个节点, 从该点至 null(树尾端)的任何路径, 都含有相同个数的黑色节点.
在树的结构发生改变时(插入或者删除操作), 往往会破坏上述条件 3 或条件 4, 需要通过调整使得查找树重新满足红黑树的条件.
image
2,TreeMap 的底层使用了红黑树来实现, 像 TreeMap 对象中放入一个 key-value 键值对时, 就会生成一个 Entry 对象, 这个对象就是红黑树的一个节点, 其实这个和 HashMap 是一样的, 一个 Entry 对象作为一个节点, 只是这些节点存放的方式不同.
3, 存放每一个 Entry 对象时都会按照 key 键的大小按照二叉树的规范进行存放, 所以 TreeMap 中的数据是按照 key 从小到大排序的.
TreeMap 总结:
程序添加新节点时, 总是从树的根节点开始比较, 即将根节点当成当前节点. 如果新增节点大于当前节点并且当前节点的右节点存在, 则以右节点作为当前节点, 如果新增节点小于当前节点并且当前节点的左子节点存在, 则以左子节点作为当前节点; 如果新增节点等于当前节点, 则用新增节点覆盖当前节点, 并结束循环 直到某个节点的左右子节点不存在, 将新节点添加为该节点的子节点. 如果新节点比该节点大, 则添加其为右子节点. 如果新节点比该节点小, 则添加其为左子节点;
来源: http://www.jianshu.com/p/538991d36046