java 数组和集合

作者: 小和大大 | 来源:发表于2022-11-01 11:25 被阅读0次

一、List和Map

6e28d28f400af4b6d139d1eeae66bd3e.png

特点

(1)传统的数组结构存储数据会在内存中开辟连续得空间，结合下标从而使得可以快速访问数据，但是删除和添加数据就很浪费资源

d2979e3a573f78f18cce5170747ef76f.png

(2)链表不需要开辟连续空间，使用指针来指向数据，因此删除和添加操作比较快，但是查询数据需要遍历全部得元素

91d7b026b0f978ed523681d0a554639c.png

(3)而哈希表[散列表]结合两者得长处，合二为一。使得哈希表比较牛掰(初始容量，数组长度默认为16，分为单指针和双指针，双指针每个元素指向前面元素同时指向后面元素)

7387cedc4acd90cf37e77fde1f0d0f55.png

(1)、List

1、可以允许重复的对象。
2、可以插入多个null元素。
3、是一个有序容器，保持了每个元素的插入顺序，输出的顺序就是插入的顺序。
4、常用的实现类有 ArrayList、LinkedList 和 Vector。ArrayList 最为流行，它提供了使用索引的随意访问，而 LinkedList 则对于经常需要从 List 中添加或删除元素的场合更为合适。

(2)、Map

1、不是collection的子接口或者实现类。Map是一个接口。
2、Map的每个 Entry 都持有两个对象，也就是一个键一个值，Map 可能会持有相同的值对象但键对象必须是唯一的。
3、TreeMap 也通过 Comparator 或者 Comparable 维护了一个排序顺序。
4、Map 里你可以拥有随意个 null 值但最多只能有一个 null 键。
5、Map 接口最流行的几个实现类是 HashMap、LinkedHashMap、Hashtable 和 TreeMap。(HashMap、TreeMap最常用)。

(3)、区别

1、list是存储单列数据的集合，map是存储双列数据的集合；
2、list中存储的数据是有序的，map中存储的数据是无序的；
3、list允许重复，map的键不能重复，值可以重复。

(4)、Array和ArrayList

Array(数组)是基于索引(index)的数据结构，它使用索引在数组中搜索和读取数据是很快的。
Array获取数据的时间复杂度是O(1),但是要删除数据却是开销很大，因为这需要重排数组中的所有数据。
List
List—是一个有序的集合，可以包含重复的元素，提供了按索引访问的方式，它继承Collection。
1、ArrayList底层采用数组实现，当使用不带参数的构造方法生成ArrayList对象时，实际上会在底层生成一个长度为10的Object类型的数组。
2、如果增加的元素个数超过10个，那么ArrayList底层会生成一个新的数组，长度为原数组的1.5倍+1，然后将原数组的内容复制到新数组中，并且后续增加的内容都会放到新的数组当中，当新的数组无法容纳增加的元素时，重读该过程。
3、对于ArrayList元素的删除操作，需要将被删除元素的后续元素向前移动，代价比较大。
4、集合当中只能放置对象的引用，无法放置原生数据类型，我们必须使用原生数据的包装类才能加入到集合当中。
5、集合当中都是Object类型，因此取出来的也是Object类型，那么必须要使用强制类型转化将其转换成真正的类型(放置进去的类型)。

二、List

1、Arraylist和Vector的区别

(1)、都实现了List接口(List接口继承了Collection接口)都是有序集合List集合规范制定(数据允许重复，可有通过索引取出数据)
(2)、ArrayList和Vector都是基于数组，因此大致代码相似。区别在于 Vector在Jdk1.0就有的古老集合，因此包含大量方法名很长的方法。 Jdk1.2开始引入集合框架引入了List接口 Vector实现了List接口因此增加了一些List接口中的方法
(3)、总体来讲ArrayList可以完全取代Vector，除非有一些老古董强制要求Vector。Vectory是线程安全的因此性能较差。ArrayList是非线程安全所以接口性能较好。即使在多线程中也应该用ArrayList，因为可以通过Collections吧ArrayList和LInkedList转换成一个线程安全的集合
例子：List ls = Collections.synchronizedList(new ArrayList<>());

2、ArrrayList、Vecor、LinkedList的存储性能和特性

(1)、ArrayList Vector ==>> 数组方式存储数据
数组元素的数据 > 实际存储的数据以及增加和插入元素
按序号索引元素
插入元素 ==>>数组移动等内存操作
索引数据快、插入数据慢
(2)、Vector ==>> synchronized方法(线程安全)
性能上较ArrayList差
(3)、LinkedList ==>> 双向链表实现存储
序号索引数据需要向前或向后遍历
插入数据时只需要记录本项的前后项即可
所以插入速度较快
线程不安全

3、ArrrayList、Vecor、LinkedList容量以及适用场景

(1)、ArrayList

特点：
1、ArrayList 内部是通过动态数组实现的，它允许对元素进行快速随机访问;
2、当数组大小不满足时需要扩容，需要将已有数组移动到新的内存空间；
3、当从 ArrayList 的中间位置插入或者删除元素时，需要对数组进行复制、移动代价比较高；
4、线程不安全。

初始容量：10初始容量：10
扩容容量：(原始容量 x 3 ) / 2 + 1。
适用场景：ArrayList 适合单线程，或多线程环境，但 List 只会被单个线程操作；随机查找和遍历，不适合插入和删除。

(2)、LinkedList

特点：
1、LinkedList 是基于双向链表存储数据的，很适合数据的动态插入和删除；
2、可根据索引值获取(get(int index)))或删除(remove(int index))节点(实现原理：通过计数索引值实现，当 index > 链表长度的1/2，从链表尾部开始遍历；反之，从链表头部开始遍历；
3、可作为队列和栈使用
4、线程不安全。
5、相对于ArrayList，LinkedList插入是更快的。因为LinkedList不像ArrayList一样，不需要改变数组的大小，也不需要在数组装满的时候要将所有的数据重新装入一个新的数组，这是ArrayList最坏的一种情况，时间复杂度是O(n)，而LinkedList中插入或删除的时间复杂度仅为O(1)。ArrayList在插入数据时还需要更新索引(除了插入数组的尾部)。
6、类似于插入数据，删除数据时，LinkedList也优于ArrayList。
7、LinkedList需要更多的内存，因为ArrayList的每个索引的位置是实际的数据，而LinkedList中的每个节点中存储的是实际的数据和前后节点的位置。

适用场景：适合单线程中，顺序读取，不适合随机读取和随机删除。

(3)、Vecor

特点：
1、其特点大致与 ArrayList 一样。
2、线程安全(因为内部方法都是通过 synchronized 关键字同步的)。

初始容量：10初始容量：10
扩容容量：若扩容系数 > 0，则将容量的值增加“扩容系数”；否则，将容量大小增加一倍。
适用场景：能不用就别用。

(4)、ArrayList相比LinkedList

顺序插入速度ArrayList会比较快，因为ArrayList是基于数组实现的，数组是事先new好的，只要往指定位置塞一个数据就好了
LinkedList则不同，每次顺序插入的时候LinkedList将new一个对象出来，如果对象比较大，那么new的时间势必会长一点，再加上一些引用赋值的操作，所以顺序插入LinkedList必然慢于ArrayList
ArrayList的遍历效率会比LinkedList的遍历效率高一些

LinkedList做插入、删除的时候，慢在寻址，快在只需要改变前后Node的引用地址
ArrayList做插入、删除的时候，慢在数组元素的批量copy，快在寻址

如果确定插入、删除的元素是在前半段，那么就使用LinkedList
如果确定插入、删除的元素在比较靠后的位置，那么可以考虑使用ArrayList

如果不能确定插入、删除是在哪儿呢？建议使用LinkedList，
一来LinkedList整体插入、删除的执行效率比较稳定，没有ArrayList这种越往后越快的情况
二来插入元素的时候，弄得不好ArrayList就要进行一次扩容，而ArrayList底层数组扩容是一个既消耗时间又消耗空间的操作

三、Map

Hash也称散列。基本原理就是把任意长度的输入，通过Hash算法变成固定长度得输出，这个映射得规则对应的就是Hash算法，而原始数据映射后得二进制串就是Hash值
entry----key----hash----index哈希值就是把各种类型的key算成统一的下标(.hashcode())

07082e086ee0dc41f936c4553dde2b47.png

Hash特点
1、从Hash值不可反向推导出原始数据
2、输入数据的微小变化也会得到完全不同的hash值，相同的数据的道相同的hash值
3、哈希算法执行高效，长文本也能快速计算出哈希
4、Hash算法冲突概率较小

Hash表在jdk1.7中使用数组+链表 jdk1.8中加入了红黑树
由于Hash的原理是将输入空间的值映射成 hash空间内，而hash值空间远小于输入的空间。
根据抽屉原理，一定会存在不同的输入被映射成相同的输出。

抽屉原理：9个抽屉放10个苹果，怎么放都会有一个抽屉里有2个及以上的苹果
(5)HashMap的继承体系

1、HashMap与HashTable简介

类似于ArrayList和LinkedList的区别， HashTable是JDK1.0 就存在的老东西，因此 HashTable是一个继承Dictionary 的古老集合。JDk1.2引入了集合框架的Map接口，HashTable也实现了Map接口，因此HashTable也增加了一些Map的方法

2、HashMap与HashTable区别

(1)、HashMap允许使用null作为Key或者Value，HashTable不允许
(2)、HashMap是线程不安全的因此性能较好，而HashTable是线程安全的因此性能较差

3、场景

多线程环境下也是用HashMap，Collections可以把HashMap转换成线程安全的集合.
例：Map map = Collections.synchronizedList(new HashMap())

4、底层一些常量与属性和构造方法

常量：

    //缺省大小
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
 
    //数组的最大长度
    static final int MAXIMUM_CAPACITY = 1 << 30;
 
    //缺省负载因子大小
    static final float DEFAULT_LOAD_FACTOR = 0.75f;
 
    //树化阈值(链表长度超过8之后并且数组长度大于64就会升级成一个树了)
    static final int TREEIFY_THRESHOLD = 8;
 
    //树降级成为链表的阈值(删除树中元素，元素=6降级为链表)
    static final int UNTREEIFY_THRESHOLD = 6;
 
    //数组长度大于64(并且某个链表长度>8)升级为红黑树
    static final int MIN_TREEIFY_CAPACITY = 64;

属性：

    //Hash表，put时初始化
    transient Node<K,V>[] table;
    
    //
    transient Set<Map.Entry<K,V>> entrySet;
 
    //当前Hash表中元素个数
    transient int size;
 
    //当前Hash表结构修改次数(插入元素或删除元素，替换不会计数)
    transient int modCount;
 
    //扩容阈值(Hash表中元素超过阈值时触发扩容，超过阈值不扩容影响查找性能。链化严重)
    int threshold;
 
    //负载因子(计算threshold = capacity数组长度   *loadFactor负载因子)
    final float loadFactor;

构造方法：

    //
    public HashMap(int initialCapacity, float loadFactor) {
        //做了逻辑校验
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal initial capacity: " +
                               initialCapacity);
        //传入数组长度超过最大长度就设置为最大长度      
        if (initialCapacity > MAXIMUM_CAPACITY)
            initialCapacity = MAXIMUM_CAPACITY;
        //负载因子<=0。。。。||不是数
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal load factor: " +
                               loadFactor);
        //赋值负载因子
        this.loadFactor = loadFactor;
        //赋值扩容阈值       位移计算只能是2的次方数导致table的长度只能是2的次方
                    传过来init。。为7计算为8，9计算为16
        this.threshold = tableSizeFor(initialCapacity);
    }
 
    //设置默认负载因子
    public HashMap() {
        this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
    }

5、put源码分析

put方法时会默认(new entry(key，value，null=指针next))
 
 
public V put(K key, V value) {
    //table的length不是特变长的情况下，让让key的hash值高于16位也参与路由运算
    return putVal(hash(key), key, value, false, true);
}
 
//实际用put向散列表插入数据
/**
     * Implements Map.put and related methods
     *
     * @param hash hash for key
     * @param key the key
     * @param value the value to put
     * @param onlyIfAbsent散列表存在欲插入的key就不插了(有就替换)
     * @param evict
     * @return previous value, or null if none
     */
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
 
    //tab：引用当前HashMap的散列表
    //p：表示当前散列表的元素
    //n：表示散列表数组的长度
    //i：表示路由寻址 结果
    
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    
    //第一次插入数据时才会初始化，只是new出来并不会初始化(好多new出来但并不用)
        //延迟初始化逻辑
    if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
 
    //寻址找桶位，刚好为null，这时直接将当前key-value转成node塞进去
        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))))
                e = p;
            else if (p instanceof TreeNode)
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            else {
                for (int binCount = 0; ; ++binCount) {
                    if ((e = p.next) == null) {
                        p.next = newNode(hash, key, value, null);
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash);
                        break;
                    }
                    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;
    }

总的来说向Vector和HashTable这种JDK1.0产物尽量不使用，除非某些api强制使用~~_{果然老东西得退休}

原文链接：https://blog.csdn.net/qq_36407919/article/details/122872643