code前端网了解HashMap和TreeMap
1的内部结构。 HashMap
1。基于哈希表的映射接口的实现。
这个实现提供了所有可选的映射函数，并允许空值和键。 （HashMap 类与 Hashtable 非常相似，只是它不是同步的并且允许 null。）该类不保证映射的顺序，尤其不保证顺序是不可变的。2。 HashMap 实例有两个影响其性能的参数：初始容量和负载因子。
容量是哈希表中桶的数量，初始容量只是哈希表创建时的容量。填充因子是衡量哈希表在其容量自动增加之前可以达到多满的程度的指标。当哈希表中的条目数量超过负载因子与当前容量的乘积时，哈希表被重新压缩（即，重建内部数据结构），使得哈希表具有大约两倍的组数。对key关键字的哈希值和桶表的长度取模，找到桶的位置。如果key的哈希值相同，存在哈希冲突（即指向同一个桶），则每次新添加的节点都作为主节点，第一个添加的就是表。HashMap 的简短总结：
1。 HashMap是一个链接矩阵（存储链表的矩阵），可以达到查询速度，可以快速得到相当于key的值； 2.影响查询速度的因素是容量和负载系数，容量高，负载系数低，查询速度快但空间浪费，反之亦然； 3、表的索引值为（关键字key，hashcode为key的哈希值，len为表的大小）：由hashcode%le的值决定，如果容量大负载因子小，获得相同索引（相同索引意味着分配到同一组）的概率很小。链表长度越小，查询速度越快。反之，如果索引相同，大链表的概率比长链表慢。 4. 在HashMap及其子类中，它们使用哈希算法来确定在哪里存储集合的元素。当HashMap初始化时，系统会创建一个具有容量长度的Entry数组。这个矩阵可以存储元素的位置。对于容器来说，每个容器都有自己的索引，系统可以根据索引快速访问组中存储的元素。 5. 每个HashMap容器一次只存储一个元素（Entry对象）。由于Entry对象可以包含指向下一个Entry的引用变量，因此可能会出现HashMap的桶中只有一个Entry，但这个Entry指向另一个Entry，从而形成一条Entry链。 6.使用上面的源代码，可以观察到HashMap在最底层将key_value对作为一个整体（Entry对象）进行处理。这个尺寸是一个 Entry 对象。当系统决定将 key_value 对存储在 HashMap 中时，它会完全忽略该条目。 value，但它只是根据 key 的哈希值确定每个条目的存储位置。注意，JDK1.8使用Node数组来存储数据，但这个节点可以是链表结构，也可以是红黑树结构。如果添加的 keys 具有相同的哈希码，则这些 keys 也位于同一个 Node 集中。在线的。如果同一个网格中key的数量不超过8个，则使用链表结构来存储。如果超过8个，则调用treeifyBin函数将链表转换为红黑树。所以即使哈希码完全相同，由于红黑树的特性，搜索特定元素只需要O(log n)的开销。换句话说，put/get 操作的最坏情况时间复杂度仅为 O(log n)。注意：key 对象必须正确实现 Compare 接口2. TreeMap
1.红黑树是一种近似平衡的二叉搜索树，可以验证任意节点是左还是右。子树之间的高度差不能超过较低子树高度的两倍。更具体地说，红黑树是满足以下条件的二叉搜索树：- 每个节点要么是红色，要么是黑色。
- 根节点必须是黑色
- 红色节点不能是连续的（即红色节点的子节点或父节点不能是红色的）。
- 对于每个节点，从该点到零（树的末端）的任何路径都包含相同数量的黑色节点。
TreeMap总结：
程序添加新节点时，总是从树的根节点开始比较，即根节点被认为是当前节点。如果新节点大于当前节点，且当前节点的右节点存在，则将右节点作为当前节点。如果新节点小于当前节点，且当前节点的左子节点存在，则将左子节点作为当前节点； if new node 如果添加的节点与当前节点相等，则将当前节点替换为新节点，循环结束，直到该节点的左右子节点不再存在，将新节点添加为子节点节点的节点。如果新节点大于该节点，则将其添加为右子节点。如果新节点小于该节点，则将其添加为左子节点。作者：程序员追风
链接：https://juejin.im/post/5d9c795c518825095e3d7461
来源：掘金。商业转载请联系作者获得许可。非商业转载请注明出处。
版权声明
本文仅代表作者观点，不代表Code前端网立场。
本文系作者Code前端网发表，如需转载，请注明页面地址。
上一篇：冒泡排序算法的Python实现 下一篇：数据结构和算法基础(前端方向)
相关文章
