java集合

可以存储基本数据，也可以存储引用数据

存储的元素必须用同一类型数据

固定长度

数组

只能存储引用数据

存储的对象可以是不同类型的

变长

集合

与数组区别

在遍历集合的时候修改（结构上的修改而非元素的修改）集合，会抛出ConcurrentModificationException异常

在设计到modCount的地方加上sychronized

使用CopyOnWriteArrayList代替ArrayList

解决办法

快速失败（fast-fail）

Collections. unmodifiableCollection(Collection c) 方法来创建一个只读集合，这样改变集合的任何操作都会抛出 Java. lang.UnsupportedOperationException 异常

确保集合不会被修改

不同的值，根据同一个哈希函数计算出来相同的哈希码

哈希冲突

概述

迭代器允许调用者在迭代过程中移除元素。

只能单向遍历

只能遍历List

可以双向遍历List

对Iterator的扩展

ListIterator

迭代器（Iterator）

ArrayBlockingQueue

LinkedBlockingQueue

BlockingQueue

双端队列

Dqueue

都是返回第一个元素

相同点

如果没有元素poll()返回nullremove()会抛出异常NoSuchElementException

不同点

poll()和 remove()区别

Queue

Object数组

每次扩容只会增加50%

只保证在修改数据时不会有并发问题；但在使用迭代器时任然会报错，迭代器在获取数据时会检查集合是否被修改过

多线程环境下，Collections 的 synchronizedList 方法将其转换成线程安全的容器后再使用

ArrayList

双向循环链表

LinkedList

比ArrayList多了一个同步，现在已不建议使用

Stack

每次扩容增加1倍

Vector

概念：有序，元素可重复，可插入null元素

List（有序）

基于 HashMap 实现的，底层采用 HashMap 来保存元素

LinkedHashSet 继承与于HashSet，并且其内部是通过 LinkedHashMap 来实现的。

LinkdeHashSet

HashSet（无序，唯一）

红黑树(自平衡的排序二叉树。)

TreeSet（有序，唯一）

NavigableSet

SortedSet

概念：无序，不重复，可插入null元素

Set（无序）

Collection

数组+链表组成的，数组是 HashMap 的主体，链表则是主要为了解决哈希冲突而存在的

比HashMap多个线程安全，已不建议使用

null不能作为键

HashTable

JDK1.8之前HashMap由数组+链表组成的，数组是HashMap的主体，链表则是主要为了解决哈希冲突而存在的（“拉链法”解决冲突）.JDK1.8以后在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为8）时，将链表转化为红黑树，以减少搜索时间

1.hashCode()计算哈希码

扰动处理：9次扰动=4次位运算+5次异或运算

JDK7

扰动处理：2次扰动=1次位运算+1次异或运算

JDK8

2.扰动处理（减少哈希冲突）

Hash计算方式

让key.hashCode() 与key.hashCode()>>16 进行异或操作高16bit补0，一个数和0异或不变，所以 hash 函数大概的作用就是：高16bit不变，低16bit和高16bit做了一个异或，目的是减少碰撞。因为bucket数组大小是2的幂，计算下标index = (table.length - 1) & hash ，如果不做 hash 处理，相当于散列生效的只有几个低 bit 位，为了减少散列的碰撞，设计者综合考虑了速度、作用、质量之后，使用高16bit和低16bit异或来简单处理减少碰撞，而且JDK8中用了复杂度 O（logn）的树结构来提升碰撞下的性能。

计算KKey的Hash值

Put方法具体流程

，resize()方法表示的在进行第一次初始化时会对其进行扩容，或者当该数组的实际大小大于其临界值(font color=\"#f15a23\

每次扩容为原来的2倍

初始大小16(2的四次方)

让 HashMap 存取高效，尽量较少碰撞，也就是要尽量把数据分配均匀，每个链表/红黑树长度大致相同。这个实现就是把数据存到哪个链表/红黑树中的算法。

取余(%)操作中如果除数是2的幂次则等价于与其除数减一的与(&)操作（也就是说hash%length==hash&(length-1)的前提是 length 是2的 n 次方；）。” 并且 采用二进制位操作 &，相对于%能够提高运算效率

加大哈希值低位的随机性，使得分布更均匀最终减少Hash冲突，两次就够了，已经达到了高位低位同时参与运算的目的；

两次扰动

算法

为啥长度为2的幂次方

键值都可以为null

继承自 HashMap，增加了一条双向链表，使得上面的结构可以保持键值对的插入顺序

LinkedHashMap（保证插入顺序）

对整个桶数组进行了分割分段(Segment)，然后在每一个分段上都用lock锁进行保护

键值都不允许为null

① 在JDK1.7的时候，ConcurrentHashMap（分段锁） 对整个桶数组进行了分割分段(Segment)，每一把锁只锁容器其中一部分数据，多线程访问容器里不同数据段的数据，就不会存在锁竞争，提高并发访问率。（默认分配16个Segment，比Hashtable效率提高16倍。） JDK1.8 的时候已经摒弃了Segment的概念，而是直接用 Node 数组+链表+红黑树的数据结构来实现，并发控制使用 synchronized 和 CAS 来操作。

ConcurrentHashMap

HashMap

IdentityHashMap

红黑树（自平衡的排序二叉树）

TreeMap

NavigableMap

SortedMap

WeakHashMap

Map

分类

java集合