list map set底层原理分析与关系

女爷i 2024-04-18 18:56 54阅读 0赞

### 数组 ArrayList LinkedList  Vector  ###

ArrayList 底层是数组，在数组的基础上提供动态大小数组的功能，扩容调用System.arrayCopy函数  
Vector 方法上增加了synchronized   
LinkedList 链表  
查找上：ArrayList快，直接下标定位，LinkedList需要指针移动  
插入节点：ArrayList需要拷贝，linkedList修改指向即可

### hashMap LinkedhashMap treeMap底层结构 ###

说明：基于jdk1.8分析  
类关系如下图

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2gyNjA0Mzk2NzM5_size_16_color_FFFFFF_t_70][]

HashMap  
底层是数组，每个数组又是链表，本质就是数组+链表  
数组元素是什么？ 链表怎么实现？  
Node 节点如下：

static class Node<K,V> implements Map.Entry<K,V> {
            final int hash;
            final K key;//
            V value;
            Node<K,V> next;//通过next指向实现链表
     .......

看下put方法

public V put(K key, V value) {
        return putVal(hash(key), key, value, false, true);
    }
    
    
    final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        // 下面获取对应数组节点
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        else {
            Node<K,V> e; K k;
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                // key 已经存在，并且是数组链表的首
                e = p;
            else if (p instanceof TreeNode)
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            else {
                for (int binCount = 0; ; ++binCount) {
                    // 尾部还没有遍历到，说明 key目前不存在
                    if ((e = p.next) == null) {
                        p.next = newNode(hash, key, value, null);
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            // 树化 稳定性能
                            treeifyBin(tab, hash);
                        break;
                    }
                    // key已存在
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;
                }
            }
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        ++modCount;
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;
    }
    Node<K,V> newNode(int hash, K key, V value, Node<K,V> next) {
        return new Node<>(hash, key, value, next);
    }

假设所有的key都发生了hash碰撞，最糟糕map会退化为链表，为了性能稳定，考虑了树化方案

/**
         * Replaces all linked nodes in bin at index for given hash unless
         * table is too small, in which case resizes instead.
         */
        final void treeifyBin(Node<K,V>[] tab, int hash) {
            int n, index; Node<K,V> e;
            if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
                resize();
            else if ((e = tab[index = (n - 1) & hash]) != null) {
                TreeNode<K,V> hd = null, tl = null;
                do {
                    TreeNode<K,V> p = replacementTreeNode(e, null);
                    if (tl == null)
                        hd = p;
                    else {
                        p.prev = tl;
                        tl.next = p;
                    }
                    tl = p;
                } while ((e = e.next) != null);
                if ((tab[index] = hd) != null)
                    hd.treeify(tab);
            }
        }

说明transient含义：  
transient Node<K,V>\[\] table; //transient的含义是不参与序列化的操作

1 怎么根据对应的key放到对应数组的位置？  
实际就是当前数组长度取余的，但是换了种写法，如下：  
hash & (length-1);  
它没有对hash表的长度取余而使用了位运算来得到索引，这是为什么呢，顿生怀疑~（PS：当时老朽就答的取余）

HashMap的初始容量和扩容都是以2的次方来进行的，那么length-1换算成二进制的话肯定所有位都为1，就比如2的3次方为8，length-1的二进制表示就是111， 而按位与计算的原则是两位同时为“1”，结果才为“1”，否则为“0”。所以h& (length-1)运算从数值上来讲其实等价于对length取模，也就是h%length

2 resize条件是什么？做了什么？put新key的时候先resize还是先insert？  
capicity 容量，即node数组大小  
fractor  加载因子，可以指定默认0.75  
threshold =factor\*capacity  
size 实际存储node个数

先insert后resize  
resize会把所有的节点重新定位

两种情况会进行resize：  
1）size>threshold的时候，需要resize进行扩充  
2）如果链表长度大于8，但是capacity小于64此时会先进行resize  
节点的链表长度大于8，并且capacity大于64的时候会进行树化

3 innsert的时候是插入尾部还是首部？  
p.next = newNode(hash, key, value, null);  
尾部，需要先遍历是否存在，如果不存在，直接再尾部插入，不需要指针移动到头部了

4 什么情况会进行树化  
如果链表长度大于8，但是capacity小于64此时会先进行resize  
节点的链表长度大于8，并且capacity大于64的时候会进行树化

public HashMap(int initialCapacity,, float loadFactor)  
initialCapacity:声明了初始容量，能确定数组大小，和加载因子共同决定threshold  
loadFactor:加载因子，默认0.75，和容量共同决定threshold

### linkedhashmap ###

为了put和遍历元素的时候能顺序相同  
LinkedHashMap可以认为是HashMap+LinkedList，即它既使用HashMap操作数据结构，又使用LinkedList维护插入元素的先后顺序  
entry  
static class Entry<K,V> extends HashMap.Node<K,V> \{  
        Entry<K,V> before, after;// 相较HashMap.Node增加前后指向  
        Entry(int hash, K key, V value, Node<K,V> next) \{  
            super(hash, key, value, next);  
        \}  
\}  
LinkedhashMap的底层还是数组+链表？  
是的，继承HashMap，那实现上到底有什么不同？  
以put方法为例，LinkedHashmap并没有重写put方法，但是重写了newNode方法，如下：

Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {
        LinkedHashMap.Entry<K,V> p =
            new LinkedHashMap.Entry<K,V>(hash, key, value, e);
        linkNodeLast(p);
        return p;
    }
    
    private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
        LinkedHashMap.Entry<K,V> last = tail;
        tail = p;
        if (last == null)
            head = p;
        else {
            p.before = last;
            last.after = p;
        }
    }

Treemap  
底层结构是什么  
由于TreeMap底层采用一颗”红黑树”来保存集合中的Entry。所以TreeMap添加元素，取出元素的性能都比HashMap低。当TreeMap添加元素时，需要通过循环找到新增的Entry的插入位置，因为比较耗性能。当取出元素时，也需要通过循环才能找到合适的Entry一样比较耗性能。但并不是说TreeMap性能低于HashMap就一无是处，TreeMap中的所有Entry总是按key根据指定的排序规则保持有序状态。

备注:红黑树是一种自平衡二叉查找树 , 它们当中每一个节点的比较值都必须大于或等于在它的左子树中的所有节点，并且小于或等于在它的右子树中的所有节点。这确保红黑树运作时能够快速的在树中查找给定的值。

现在我们来观察TreeMap的put(K key,V value)方法，该方法将Entry放入TreeMap的Entry链，并维护该Entry链的有序状态。下面列出源码:

public V put(K key, V value) {
          //定义一个t来保存根元素
            Entry<K,V> t = root;
            //如果t==null，表明是一个空链表
            if (t == null) {
            //如果根节点为null，将传入的键值对构造成根节点（根节点没有父节点，所以传入的父节点为null）
                root = new Entry<K,V>(key, value, null);
                //设置该集合的size为1
                size = 1;
                //修改此时+1
                modCount++;
                return null;
            }
            // 记录比较结果
            int cmp;
            Entry<K,V> parent;
            // 分割比较器和可比较接口的处理
            Comparator<? super K> cpr = comparator;
            // 有比较器的处理，即采用定制排序
            if (cpr != null) {
                // do while实现在root为根节点移动寻找传入键值对需要插入的位置
                do {
                    //使用parent上次循环后的t所引用的Entry
                    // 记录将要被掺入新的键值对将要节点(即新节点的父节点)
                    parent = t;
                    // 使用比较器比较父节点和插入键值对的key值的大小
                    cmp = cpr.compare(key, t.key);
                    // 插入的key较小
                    if (cmp < 0)
                        t = t.left;
                    // 插入的key较大
                    else if (cmp > 0)
                        t = t.right;
                    // key值相等，替换并返回t节点的value(put方法结束)
                    else
                        return t.setValue(value);
                } while (t != null);
            }
            // 没有比较器的处理
            else {
                // key为null抛出NullPointerException异常
                if (key == null)
                    throw new NullPointerException();
                Comparable<? super K> k = (Comparable<? super K>) key;
                // 与if中的do while类似，只是比较的方式不同
                do {
                    parent = t;
                    cmp = k.compareTo(t.key);
                    if (cmp < 0)
                        t = t.left;
                    else if (cmp > 0)
                        t = t.right;
                    else
                        return t.setValue(value);
                } while (t != null);
            }
            // 没有找到key相同的节点才会有下面的操作
            // 根据传入的键值对和找到的“父节点”创建新节点
            Entry<K,V> e = new Entry<K,V>(key, value, parent);
            // 根据最后一次的判断结果确认新节点是“父节点”的左孩子还是又孩子
            if (cmp < 0)
                parent.left = e;
            else
                parent.right = e;
            // 对加入新节点的树进行调整
            fixAfterInsertion(e);
            // 记录size和modCount
            size++;
            modCount++;
            // 因为是插入新节点，所以返回的是null
            return null;
        }

上面程序中的两个do…while就是实现”排序二叉树”的关键算法。每当程序希望添加新节点时，总是从树的根节点开始比较，即将根节点当成当前节点。

如果新增节点大于当前节点且当前节点的右子节点存在，则以右子节点作为当前节点。并继续循环  
如果新增节点小于当前节点且当前节点的左子节点存在，则以左子节点作为当前节点。并继续循环  
如果新增节点等于当前节点，则新增节点覆盖当前节点，并结束循环。  
当TreeMap根据key来取出value时，TreeMap对应的方法如下:

public V get(Object key) {
         //根据key取出Entry
         Entry<K,V> p = getEntry(key);
         //取出Entry所包含的value
         return (p==null ? null : p.value);
     }

现在我们可以知道，其实get(Object key)方法实质上是由getEntry()方法实现的。现在我们来看getEntry(Object key)的源码:

final Entry<K,V> getEntry(Object key) {
        // 如果有比较器，返回getEntryUsingComparator(Object key)的结果
        if (comparator != null)
            return getEntryUsingComparator(key);
        // 查找的key为null，抛出NullPointerException
        if (key == null)
            throw new NullPointerException();
        // 如果没有比较器，而是实现了可比较接口
        //将key强制转换为Comparable接口
        Comparable<? super K> k = (Comparable<? super K>) key;
        // 获取根节点
        Entry<K,V> p = root;
        // 从根节点开始对树进行遍历查找节点
        while (p != null) {
            // 把key和当前节点的key进行比较
            int cmp = k.compareTo(p.key);
            // key小于当前节点的key
            if (cmp < 0)
                // p “移动”到左节点上
                p = p.left;
            // key大于当前节点的key
            else if (cmp > 0)
            // p “移动”到右节点上
    　　　　p = p.right;
            // key值相等则当前节点就是要找的节点
            else
                // 返回找到的节点
                return p;
            }
        // 没找到则返回null
        return null;
    }

getEntry(Object obj)方法也是充分利用排序二叉树的特性来搜索目标Entry。程序依然从二叉数的根节点开始，如果被搜索节点大于当前节点，程序向”右子树”搜索，如果小于，则向”左子树”搜索。如果相等则说明找到了指定节点。

我们观察到当该TreeMap采用了定制排序。在采用定制排序的方式下，TreeMap采用getEntryUsingComparator(key)方法来根据key获取Entry。

final Entry<K,V> getEntryUsingComparator(Object key) {
        K k = (K) key;
        // 获取比较器
    Comparator<? super K> cpr = comparator;
    // 其实在调用此方法的get(Object key)中已经对比较器为null的情况进行判断，这里是防御性的判断
    if (cpr != null) {
        // 获取根节点
            Entry<K,V> p = root;
            // 遍历树
            while (p != null) {
                // 获取key和当前节点的key的比较结果
                int cmp = cpr.compare(k, p.key);
                // 查找的key值较小
                if (cmp < 0)
                    // p“移动”到左孩子
                    p = p.left;
                // 查找的key值较大
                else if (cmp > 0)
                    // p“移动”到右节点
                    p = p.right;
                // key值相等
                else
                    // 返回找到的节点
                    return p;
            }
    }
    // 没找到key值对应的节点，返回null
        return null;
    }

其实getEntry()和getEntryUsingComparator()这两个方法实现思路几乎完全类似。只是前者对自然排序的TreeMap获取有效，后者对定制排序的TreeMap有效。

通过上述源码其实不难看出，TreeMap这个工具类的实现其实很简单。或者说，从本质上来说TreeMap就是一棵”红黑树”，每个Entry就是一个节点。

### key value 哪些可以为空？哪些不可为空？ why ###

treemap 不允许null键  时间复杂度log(n)  
因为treemap是有序的，其所有key都需要compare来进行排序，null是不能进行compare的

hashmap 允许 时间复杂度 常量，，key为null的时候，hash值取0  
hashtable 类似hashMap，很多方法增加synchronized 建值均不允许为空  
hashtable好像是因为遗留问题key value都不允许为空

### LinkedHashMap 和 TreeMap的有序性一样吗？ ###

不一样 前者是直接按照插入的顺序来排序，后者按照key进行comparator

### Set  ###

HashSet 底层就是Hashmap，value是固定PRESENT，即一个new Object()  
TreeSet 相对HashSet,TreeSet的优势是有序  
treeset怎么实现有序的,treeset的底层是treemap  
TreeSet中的元素必须实现Comparable接口并重写compareTo()方法，TreeSet判断元素是否重复 、以及确定元素的顺序 靠的都是这个方法；  
①对于Java类库中定义的类，TreeSet可以直接对其进行存储，如String，Integer等,因为这些类已经实现了Comparable接口);  
②对于自定义类，如果不做适当的处理，TreeSet中只能存储一个该类型的对象实例，否则无法判断是否重复。

LinkedHashSet 底层实现LinkedHashMap

### 解决哈希冲突的常用方法有： ###

开放定址法  
基本思想是：当关键字key的哈希地址p=H（key）出现冲突时，以p为基础，产生另一个哈希地址p1，如果p1仍然冲突，再以p为基础，产生另一个哈希地址p2，…，直到找出一个不冲突的哈希地址pi ，将相应元素存入其中。

再哈希法  
这种方法是同时构造多个不同的哈希函数：  
Hi=RH1（key）  i=1，2，…，k  
当哈希地址Hi=RH1（key）发生冲突时，再计算Hi=RH2（key）……，直到冲突不再产生。这种方法不易产生聚集，但增加了计算时间。

链地址法  
这种方法的基本思想是将所有哈希地址为i的元素构成一个称为同义词链的单链表，并将单链表的头指针存在哈希表的第i个单元中，因而查找、插入和删除主要在同义词链中进行。链地址法适用于经常进行插入和删除的情况。

建立公共溢出区  
这种方法的基本思想是：将哈希表分为基本表和溢出表两部分，凡是和基本表发生冲突的元素，一律填入溢出表。

set系列是否可以改造？怎么移除value？

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2gyNjA0Mzk2NzM5_size_16_color_FFFFFF_t_70]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/1325a26f02bf414e8a1ccec4daf2f7a3.png