List

List 有序集合，可重复，提供按索引方式访问，继承Collection。

List有两个重要的实现类 ArrayList、LinkedList。Vector是线程安全的

ArrayList的toArray方法返回一个数组。

ArrayList的AsList方法返回一个列表。

ArrayList底层实现是Array,数组扩容实现。System.arraycopy()

LikedList是一个双链表，在添加和删除元素时具有比ArrayList更好的性能，

get、set方面弱于ArrayList, 这些对比都是指数据量很大或者操作频繁的情况。

Vector是同步的，add/remove/sort/subList方法都加synchronized

数组和arrayList 区别

空间大小

1. Array的空间大小是固定的，

空间不够时也不能再次申请，所以需要事前确定合适的空间大小。

1. ArrayList的空间是动态增长的，

如果空间不够，它会创建一个空间比原空间大1.5倍的新数组，

然后将所有元素复制到新数组中，接着抛弃旧数组。

而且，每次添加新的元素的时候都会检查内部数组的空间是否足够。

扩容 Arrays.copyOf()

优点：Array获取数据的时间复杂度是O(1),但是要删除数据确实开销很大，

因为这需要重排数组中所有数组（因为删除数据以后，需要吧后面所有的数据前移，重新搞一个数组）。

缺点：数组初始化必须指定初始化长度，否则报错。

public static native void Arrays.arraycopy(Object src, int srcPos, Object dest, int destPos,   int length);

src - 源数组。

srcPos - 源数组中的起始位置。

dest - 目标数组。

destPos - 目的地数据中的起始位置。

length - 要复制的源数组元素的数量。

LinkedList 的双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，

分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，

都可以很方便地访问它的前驱结点和后继结点。

例如：

数组下标为什么从0开始？

历史和语言设计传统

Java 语言在设计时受到了 C 和 C++ 语言的影响。

C 语言数组下标就是从 0 开始的，Java 继承了这种设计方式，

以保持和底层系统编程以及前辈语言的兼容性，方便熟悉这些语言的程序员学习和使用 Java。

内存地址计算

在 Java 中，数组是一块连续的内存空间。数组元素的内存地址计算方式和下标紧密相关。

对于一个数组arr，计算元素arr[i]的内存地址时，

是通过数组的首地址加上i乘以单个元素占用的字节数来得到的。

当从 0 开始计数时，第一个元素的偏移量为 0，

这种计算方式简单直接，方便编译器和 JVM（Java 虚拟机）高效地定位元素。

寻址公式是：baseAddress +i *dataTypeSize, 计算下标的内存地址快。

baseAddress 首地址 和dataTypeSize 该类型宽度（占用字节数）

https://www.cnblogs.com/xixixing/p/17783149.html

与数据结构和算法的契合

许多数据结构和算法在实现和描述过程中，基于 0 开始计数更自然。

比如在循环遍历数组、进行二分查找等操作时，从 0 开始计数能更好地和数学模型及算法逻辑相匹配，

减少计算中的调整和转换步骤。

//数组转list【对象引用】
List<String> list = Arrays.asList("1", "3", "7", "5");

数组转list，数组内容修改了，list也会改变，因为底层：对象引用，没有创建新的数组。
//list转数组【数组拷贝不会有影响】
String[] objects = list.toArray( new Strng[list.size() ]);
for (String o : objects) {
    System.out.println(o);
}

ArrayList 、LinkedList、HashMap查找元素时间复杂度

ArrayList 根据下标O(1), 根据值查找O(N)，

LinkedList查找值的复杂度O(N),

HashMap 哈希函数不冲突O(1) ,冲突最坏情况O(n)

ArrayList 和 LinkedList 是 Java 中常用的两种线性数据结构，它们在查找操作上的时间复杂度有所不同。

ArrayList 是基于数组实现的动态列表，在查找元素时，时间复杂度为 O (1) 或 O (n)，

这取决于查找方式。如果是通过索引直接访问元素，由于数组在内存中是连续存储的，

计算机可以通过简单的地址计算直接定位到指定索引的元素，所以时间复杂度为 O (1)。

但如果是按值查找元素，需要遍历数组中的元素，从第一个元素开始逐个比较，

直到找到目标元素或遍历完整个数组，这种情况下平均时间复杂度为 O (n)，n 为数组中元素的个数。

寻址公式是：baseAddress + i *dataTypeSize, 计算下标的内存地址。

baseAddress 首地址 和dataTypeSize 该类型宽度（占用字节数）

LinkedList 是基于链表实现的列表，查找元素时时间复杂度为 O (n)。

无论是通过索引查找还是按值查找，都需要从链表的头节点（或尾节点，取决于查找方向）

开始逐个遍历节点。因为链表中的节点在内存中不是连续分布的，

不能像数组那样直接通过地址计算定位元素，

所以每次查找都需要沿着链表的指针依次访问下一个节点，

直到找到目标元素或遍历完整个链表，因此时间复杂度为 O (n)。

哈希表查找值的时间复杂度在理想情况下为 O (1)，但在最坏情况下会退化为 O (n)。

在理想状况下，哈希函数能将每个键均匀地映射到哈希表的各个槽中，没有冲突。

当查找某个值时，通过哈希函数计算键的哈希值，直接定位到对应的槽，

就能马上找到值，这个过程的时间复杂度是常数级别的 O (1)。

然而，实际应用中，由于哈希表的存储空间有限，不同的键可能会映射到相同的槽，即产生冲突。

当冲突解决策略不够好时，比如采用简单的线性探测法，随着插入元素的增多，

冲突会越来越严重，可能会形成很长的冲突链。在这种最坏的情况下，

查找一个值就需要遍历冲突链上的所有元素，时间复杂度会退化为与元素个数 n 相关的 O (n)。

不过，通过合理选择哈希函数、调整哈希表的大小和采用高效的冲突解决策略，

可以将哈希表查找的时间复杂度尽可能地接近理想情况的 O (1)。

Map 

HashTable /LinkedHashMap /TreeMap  /ConcurrentHashMap/weakHashMap/EnumMap键是枚举类型

HashMap

1. Key-value 数据结构，存取无序，键和值都可以为null,键是唯一的

2. 是Node数组+链表[链表是解决hash冲突的 拉链法]/红黑树（JDK1.8增加了红黑树部分）;

优化的部分就是把链表结构变成了红黑树。原来jdk1.7的优点是增删效率高，

于是在jdk1.8的时候，不仅仅增删效率高，而且查找效率也提升了。从链表的o(n)降低为o(logn)。

3.非线程安全，默认容量为16，加载因子默认阈值0.75

4.扩容2的N次幂 (16,32,48,64,128,256）

查询时间复杂度数组o(1),链表o(n),红黑树 o(logn)

JDK1.8,链表的深度>8，且数组容量大于64时，扩容的时候会把链表转成红黑树，

当红黑树的节点深度小于等于6时，红黑树会转为链表结构。

【1亿个出现6个的概率转红黑树】

树的特点：短(深度)、旋转、查询快

Hash算法解决冲突

开放定址法： 一旦发生了冲突，就去寻找下一个空的散列地址。

再哈希法： 多个不同的Hash函数，当发生冲突时，使用第二个，第三个，…。

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

www.cnblogs.com/lyfstorm/p/11044468.html

目前流行的 Hash 算法包括 MD5、SHA-1 和 SHA-2。

信息安全：文件校验、数字签名、鉴权协议

Put

1. 对key做hash
2. Put时若数组为空则创建一个新数组 resize()扩容
3. 根据hash算法计算在数组的存在位置是否冲突，

不冲突直接插入newNode(hash, key, value, null);插入到数组中即可。

1. 冲突的话，判断数组中的元素是否与插入的key一样，若相同直接替换旧值。
2. 判断插入数据结构是链表还是红黑树；

若是红黑树putTreeVal(),若是链表便利数组是否存在，不存在直接newNode(hash, key, value, null).

（jdk1.8尾部插入新的节点，1.7是头插）。

注意一点：不存在并且在链表末尾插入元素的时候，会判断binCount >= TREEIFY_THRESHOLD - 1。

也就是判断当前链表的长度是否大于阈值8，如果大于那就会把当前链表转变成红黑树，

方法是而且数组的长度不小于64，treeifyBin(tab, hash)而又当小于6时，则转化为链表存储。

Get

1. 获取key的hash值。
2. 从链表的首节点开始查询，如果key相同就返回。
3. 遍历红黑树/链表有相同的返回，没有返回null。

resize()

Threshold=数组长度*0.75  /ˈθreʃhəʊld/

大于threshold扩容

1. 排查异常情况  整数最小范围<容量<整数最大范围
2. 扩容2倍新建数组
3. 把旧数组的数据移动到新数组中

计算hash值

取key的hashCode值、高位运算、取模运算。

方法一：

static final int hash(Object key) {   //jdk1.8 & jdk1.7

     int h;

     // h = key.hashCode() 为第一步 取hashCode值

     // h ^ (h >>> 16)  为第二步 高位参与运算

     return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);

}

方法二：

static int indexFor(int h, int length) {  //jdk1.7的源码，jdk1.8没有这个方法，但是实现原理一样的

     return h & (length-1);  //第三步 取模运算

}

参考：

HashMap实现原理、源码解析（jdk1.8） - 简书

https://zhuanlan.zhihu.com/p/79219960

map四种便利

public static void main(String[] args) {

    Map<String, String> map = new HashMap<String, String>();

    map.put("1", "value1");

    map.put("2", "value2");

    map.put("3", "value3");

    //第一种：普遍使用，二次取值

    System.out.println("通过Map.keySet遍历key和value：");

    for (String key : map.keySet()) {

        System.out.println("key= "+ key + " and value= " + map.get(key));

    }

    //第二种

    System.out.println("通过Map.entrySet使用iterator遍历key和value：");

    Iterator<Map.Entry<String, String>> it = map.entrySet().iterator();

    while (it.hasNext()) {

        Map.Entry<String, String> entry = it.next();

        System.out.println("key= " + entry.getKey() + " and value= " + entry.getValue());

    }

    //第三种：推荐，尤其是容量大时

    System.out.println("通过Map.entrySet遍历key和value");

    for (Map.Entry<String, String> entry : map.entrySet()) {

        System.out.println("key= " + entry.getKey() + " and value= " + entry.getValue());

    }

    //第四种

    System.out.println("通过Map.values()遍历所有的value，但不能遍历key");

    for (String v : map.values()) {

        System.out.println("value= " + v);

    }

 }

lambda表达式forEach遍历

map.forEach((k, v) -> System.out.println("key = " + k + ", value = " + v));

List、Set和Map接口的特点与常用的实现类 - Java面试题

https://blog.csdn.net/q5706503/article/details/85122343

数组和MAP访问数据谁更快

若是比较某个固定元素的访问速度，那是数组快

若是随机访问，自然是BTREE的map快。

hashMap 存100个键值对，初始化高，应该设为多少

HashMap的实例有两个参数影响其性能：初始容量和加载因子 0.75。

指定容量大小:2的n次方(幂)。

HashMap 1. 7 VS 1.8不安全体现

1.7 node数组加单链表，1.8后链表冲突多了红黑树；

1.7中新增节点采用头插法，

1.8中新增节点采用尾插法（避免逆序且链表死循环的问题）

让HashMap线程安全 Map m = Collections.synchronizeMap(hashMap);

原因

jdk1.7HashMap线程不安全主要是发生在扩容函数中，

其中调用了HshMap的transfer()。方法在执行数组扩容操作时，数据会重新定位新数组中索引，

并采用头插法将元素迁移到新数组中。头插法会将链表的顺序翻转，

这也是形成死循环的关键点。如何造成死循环以及数据丢失的。

改善：

数据丢失、死循环已经在在JDK1.8中已经得到了很好的解决，

1.8的源码会发现找不到HashMap#transfer()，

JDK1.8直接在HashMap#resize()中完成了数据迁移。

HashMap线程不安全的体现：

JDK1.7 HashMap线程不安全体现在：死循环、数据丢失  

JDK1.8 HashMap线程不安全体现在：数据覆盖

hashMap /hashTable/concurrentHashMap区别

为什么HashMap线程不安全？以及实现HashMap线程安全的解决方案_hashmap线程安全吗 什么解决方案-CSDN博客

多线程使用hashmap

  Collections.synchronizedMap(Map)创建线程安全的map集合

  Hashtable 锁的全表

ConcurrentHashMap(1.5分段锁、1.8是cas)：性能和效率好

ConcurrentHashMap

Hashmap    key value 可以为空,

ConcurrentHashMap  key value 不可以为空(put 有校验，防止出现线程问题)

底层数据结构：

Jdk1.7采用的是分段数组+链表

Jdk1.8采用的是数组+链表/红黑二叉树,与hashMap一致。

加锁的方式

    1.7采用Segment分段锁，底层使用的是ReentrantLock。

1.8采用CAS添加新节点，采用synchronized锁定链表/红黑二叉树的首节点，

相对segment分段锁粒度更细，性能更好。Get时都用Volatile修饰，无需加锁。

HashTable(全表锁)VS ConcurrentHashMap

实现：

ConcurrentHashMap 在 Java 7 采用分段锁（segment），

一个哈希表分成若干个小的哈希表，每个小的哈希表有自己的锁，同一时刻可以被多个线程访问。

在 Java 8 中，采用了 CAS 操作来替代了分段锁，提高了性能。

HashTable(全表锁)get/put所有相关操作都是synchronized的，这相当于给整个哈希表加了一把大锁，

多线程访问的时候，只要有一个线程访问或操作该对象，那其他线程只能阻塞。

性能：

ConcurrentHashMap 采用分段锁（Java 5）和 CAS 操作（Java 8），

在多线程场景下，锁的竞争更加细粒度，可以提供更好的并发性能。

Hashtable 采用 synchronized 关键字，可以确保线程安全，但在高并发情况下，

竞争激烈会导致性能下降。

HashMap VS TreeMap

HashMap :适用于在Map中插入、删除和定位元素。

Treemap:适用于按自然顺序或自定义顺序遍历键(key)。

TreeMap实现SortMap接口，能够把它保存的记录根据键排序,默认是按键值的升序排序

TreeMap的value可以是null，（没有自定义比较器）key不能为null,compareTo方法会发生空指针异常。

HashMap和HashTable区别

1、两者父类不同

HashMap是继承自AbstractMap类，而Hashtable是继承自Dictionary类。

它们都同时实现了map、Cloneable（可复制）、Serializable（可序列化）这三个接口。

2、对null的支持不同

HashTable：key和value都不能为null。

HashMap：key可以为null，但是这样的key只能有一个，

3、安全性不同

HashMap是线程不同步的。

HashTable是线程同步的（全表锁），每个方法上都有synchronized 关键字，

ConcurrentHashMap（concurrent并发包），它是HashTable的替代，

1. 初始容量大小和每次扩充容量大小不同  

HashMap默认的初始化大小为16，之后每次扩容，容量变为原来的 2的整数次幂

Hashtable 默认的初始大小为11，之后每次扩容，容量变为原来的 2n+1。

HasmMap和HashSet的区别

weakHashMap

它是一个“弱键”，它的Key值和Value都可以是null，

其Map中如果这个Key值指向的对象没被使用，此时触发了GC，该对象就会被回收掉的。

其原理主要是使用的WeakReference和ReferenceQueue实现的，

其key就是weakReference，而ReferenceQueue中保存了被回收的 Key-Value。

原文链接：java中Map有哪些实现类和使用场景_java hashmap、treemap、linkedhashmap、concurrenthashm-CSDN博客

HashMap底层实现原理及扩容机制 - dadapeng - 博客园

HashMap原理 — 扩容机制及存取原理 - 简书

【大厂面试题系列】：JDK7、8 HashMap的get()、put()方法流程_hashmap.pualll-CSDN博客