企业的网站推广意义,西宁市网站建设官网,网站建设服务器费用,门户网站开发 价格1.源码 java1.7 hashMap 底层实现是数组链表
java1.8 对上面进行优化 数组链表红黑树
2.hashmap 是怎么保存数据的。
在hashmap 中有这样一个结构 Node implenets Map.entity{hashkeyvaluenext} 当我们向hashMap 中放入数据时#xff0c;其实就是一个
Enity{keyvaue}在存之…1.源码 java1.7 hashMap 底层实现是数组链表
java1.8 对上面进行优化 数组链表红黑树
2.hashmap 是怎么保存数据的。
在hashmap 中有这样一个结构 Node implenets Map.entity{hashkeyvaluenext} 当我们向hashMap 中放入数据时其实就是一个
Enity{keyvaue}在存之前会把这个Entity 转成Node
怎么转的如下
根据Entity 的key 通过hash 算出一个值 当成Node 的 hash ,key vlaue ,复制到Node 中对于没有产生hash 冲突前Node 的next 是null. 复制完成后还需要通过Entity 对象的hash 算出 该 Entiry对象 具体应该放在 hashMap 的那个位置。计算如下 Hash(lenth-1) 得到的值就是hashMap 对应具体的位置。lentth是当前hashMap 的长度。‘
解决hash 冲突
就是不同的元素通过 Hash(lenth-1) 公式算出的位置相同现在就启动了链表单项链表挂在了当前位置的下面而链表的元素怎么关联呢就用到了Node 的next next的值就是该链表下一个元素在内存中的地址。
jdk1.7 就是这样处理的而到了 1.8 以后就引用了红黑树1.8以后这个链表只让挂7个元素超过七个就会转成一个红黑树进行处理最多是64超多64 就会重新拆分。
当红黑树下挂的节点小于等于6的时候系统会把红黑树转成链表。 Node 在jdk1.8之前是插入l链表头部的在jdk1.8中是插入链表的尾部的。
hashMap 扩容
hashMap 会根据 当前的hashMap 的存储量达到 160.7512 的时候就是扩容 16232 依次类推下去。2倍扩容。
扩容后元素是如何做到均匀分的。 对上面的总结 LinkedHashMap 源码详细分析JDK1.8
我针对LinkedHashMap 的总结有一下几点
1.LinkedHashMap 继承自 HashMap所以它的底层仍然是基于拉链式散列结构。该结构由数组和链表红黑树 在此基础上LinkedHashMap 增加了一条双向链表保持遍历顺序和插入顺序一致的问题。
2. 在实现上LinkedHashMap 很多方法直接继承自 HashMap比如put remove方法就是直接用的父类的仅为维护双向链表覆写了部分方法get方法是重写的。
3.LinkedHashMap使用的键值对节点是Entity 他继承了hashMap 的Node,并新增了两个引用分别是 before 和 after。这两个引用的用途不难理解也就是用于维护双向链表.
4.链表的建立过程是在插入键值对节点时开始的初始情况下让 LinkedHashMap 的 head 和 tail 引用同时指向新节点链表就算建立起来了。随后不断有新节点插入通过将新节点接在 tail 引用指向节点的后面即可实现链表的更新
5.LinkedHashMap 允许使用null值和null键 线程是不安全的虽然底层使用了双线链表但是增删相快了。因为他底层的Entity 保留了hashMap node 的next 属性。
6.如何实现迭代有序
重新定义了数组中保存的元素Entry继承于HashMap.node)该Entry除了保存当前对象的引用外还保存了其上一个元素before和下一个元素after的引用从而在哈希表的基础上又构成了双向链接列表。仍然保留next属性所以既可像HashMap一样快速查找
用next获取该链表下一个Entry也可以通过双向链接通过after完成所有数据的有序迭代.
7.竟然inkHashMap 的put 方法是直接调用父类hashMap的但在 HashMap 中put 方法插入的是 HashMap 内部类 Node 类型的节点该类型的节点并不具备与 LinkedHashMap 内部类 Entry 及其子类型节点组成链表的能力。那么LinkedHashMap 是怎样建立链表的呢 虽然linkHashMap 调用的是hashMap中的put 方法但是linkHashMap 重写了了一部分方法其中就有 newNode(int hash, K key, V value, Node e)linkNodeLast(LinkedHashMap.Entry p) 这两个方法就是 第一个方法就是新建一个 linkHasnMap 的Entity 方法而 linkNodeLast 方法就是为了把Entity 接在链表的尾部。 8.链表节点的删除过程
与插入操作一样LinkedHashMap 删除操作相关的代码也是直接用父类的实现但是LinkHashMap 重写了removeNode()方法 afterNodeRemoval方法该removeNode方法在hashMap 删除的基础上有调用了afterNodeRemoval 回调方法。完成删除。
删除的过程并不复杂上面这么多代码其实就做了三件事
根据 hash 定位到桶位置遍历链表或调用红黑树相关的删除方法从 LinkedHashMap 维护的双链表中移除要删除的节点
TreeMap 和SortMap
1.TreeMap实现了SortedMap接口保证了有序性。默认的排序是根据key值进行升序排序也可以重写comparator方法来根据value进行排序*具体取决于使用的构造方法*。不允许有null值null键。TreeMap是线程不安全的。
**2.TreeMap基于*红黑树Red-Black tree实现*。**TreeMap的基本操作 containsKey、get、put 和 remove 的时间复杂度是 log(n) 。
public class SortedMapTest {public static void main(String[] args) {SortedMapString, String sortedMap new TreeMapString, String();sortedMap.put(1, a);sortedMap.put(5, b);sortedMap.put(2, c);sortedMap.put(4, d);sortedMap.put(3, e);SetEntryString, String entry2 sortedMap.entrySet();for (EntryString, String temp : entry2) {System.out.println(修改前 sortedMap: temp.getKey() 值 temp.getValue());}System.out.println(\n);//这里将map.entrySet()转换成listListMap.EntryString, String list new ArrayListMap.EntryString, String(entry2);Collections.sort(list, new ComparatorMap.EntryString, String() {Overridepublic int compare(EntryString, String o1, EntryString, String o2) {
// TODO Auto-generated method stubreturn o1.getValue().compareTo(o2.getValue());}});for (Map.EntryString, String temp : list) {System.out.println(修改后 sortedMap: temp.getKey() 值 temp.getValue());}}}附加点上面没有讲到的面试题
1 HashMap特性 HashMap的特性HashMap存储键值对实现快速存取数据允许null键/值线程不安全不保证有序(比如插入的顺序)。
2 HashMap中hash函数怎么是是实现的还有哪些 hash 的实现方式 1. 对key的hashCode做hash操作高16bit不变低16bit和高16bit做了一个异或 2. h (length-1); //通过位操作得到下标index。
3 扩展问题1当两个对象的hashcode相同会发生什么 因为两个对象的Hashcode相同所以它们的bucket位置相同会发生“碰撞”。HashMap使用链表存储对象这个Entry(包含有键值对的Map.Entry对象)会存储在链表中。
4 扩展问题2抛开 HashMaphash 冲突有那些解决办法 开放定址法、链地址法、再哈希法。
5如果两个键的hashcode相同你如何获取值对象 重点在于理解hashCode()与equals()。 通过对key的hashCode()进行hashing并计算下标( n-1 hash)从而获得buckets的位置。两个键的hashcode相同会产生碰撞则利用key.equals()方法去链表或树java1.8中去查找对应的节点。
6 针对 HashMap 中某个 Entry 链太长查找的时间复杂度可能达到 O(n)怎么优化 将链表转为红黑树实现 O(logn) 时间复杂度内查找。JDK1.8 已经实现了。
7.如果HashMap的大小超过了负载因子(load factor)定义的容量怎么办 扩容。这个过程也叫作rehashing因为它重建内部数据结构并调用hash方法找到新的bucket位置。 大致分两步 1.扩容容量扩充为原来的两倍2 * table.length 2.移动对每个节点重新计算哈希值重新计算每个元素在数组中的位置将原来的元素移动到新的哈希表中。 (如何计算上面讲的有)
8 为什么String, Interger这样的类适合作为键 String, Interger这样的类作为HashMap的键是再适合不过了而且String最为常用。 因为String对象是不可变的而且已经重写了equals()和hashCode()方法了。 1.不可变性是必要的因为为了要计算hashCode()就要防止键值改变如果键值在放入时和获取时返回不同的hashcode的话那么就不能从HashMap中找到你想要的对象。不可变性还有其他的优点如线程安全。 注String的不可变性可以看这篇文章《【java基础】浅析String》。 2.因为获取对象的时候要用到equals()和hashCode()方法那么键对象正确的重写这两个方法是非常重要的。如果两个不相等的对象返回不同的hashcode的话那么碰撞的几率就会小些这样就能提高HashMap的性能。
9.hashmap.put 为什么是线程不安全的。很重要
正常情况下 hashmap 在保存数据时底层是数组链表红黑树 但是 你去源码中看时i发现子啊hashMap 底层没有加任何的多线程中的锁机制比如 synchronize修饰 所以在多线程的情况下 hashMap 的单项链表
可能会变成一个环形的链表所以这个链表上的Next元素的指向永远不为null, 所以在遍历的时候就是死循环啊。
9.1HashMap在put的时候插入的元素超过了容量由负载因子决定的范围就会触发扩容操作就是rehash这个会重新将原数组的内容重新hash到新的扩容数组中在多线程的环境下存在同时其他的元素也在进行put操作如果hash值相同可能出现同时在同一数组下用链表表示造成闭环导致在get时会出现死循环所以HashMap是线程不安全的
9.2 HashMap底层是一个Entry数组当发生hash冲突的时候hashmap是采用链表的方式来解决的在对应的数组位置存放链表的头结点。对链表而言新加入的节点会从头结点加入。在hashmap做put操作的时候会调用到以上的方法。现在假如A线程和B线程同时对同一个数组位置调用addEntry两个线程会同时得到现在的头结点然后A写入新的头结点之后B也写入新的头结点那B的写入操作就会覆盖A的写入操作造成A的写入操作丢失 10 ,hashmap 初始化时就生了一个长度为16 的数组。
1.1 为什么初始化时16 而不是别的数字
1.其实是4或者8 只要是2的N次幂就行因为hashMap put 元素时会根据key 进行运算得到一个位置运算就是根据key的hash值hashMap的长度-1hashlength-1
假如hashMap的长度为16 补充运算时都是1才为1,其他情况都为0
hash值 1010 1010 1000 0000 … 1010 lennth-1 0111
你会发现不管hash值为多少只要 length 的长度是2的N次幂 那么length-1 的二进制最后一位就是1,所以 hash值上length-1 最后得到的二进制数字的末位可能是1 也可能是0,
如果 其长度不是2的n次幂比如 15 那么15-1 14 的 二进制 0110那么遇上hash 的到二进制末位永远就是0了 这就侧面的表明了通过计算出来的元素位置的分散性。
为什么不选4,8 这些也是2的N次幂作为扩容初始化值呢其实8 也行4 也行但是 我的java 是c语言写的而c语言是由汇编语言而汇编的语言来源是机器语言而汇编的语言使用的就是16进制对于经验而言当然就选16喽。
