Java基础-集合_set集合能用迭代器

Java基础

一、java为什么可以跨平台

java程序编译之后生成的并不是能够被硬件系统直接运行的代码，而是一种中间语言——字节码。然后不同的硬件平台可以安装不用的java虚拟机，然后由java虚拟机再把字节码翻译成硬件平台能够执行的代码。所以对于java程序员来说并不需要知道硬件平台是什么，所以java可以跨平台。

二、java集合

1、java中数组和集合的区别

①数组能存放基本数据类型和对象；集合只能放对象（数组和集合存放的对象都是对象的引用地址）；
②数组的容量固定无法改变；集合类的容量可以动态改变；
③数组无法判断有多少个元素，只能知道数组的容量；集合的size（）可以获得确切的元素个数
④数组的只能采用顺序表的方式实现；集合可以采用多种实现方式适用于不同的场合
⑤集合以类的形式存在，也就是说它具有java类的封装、继承、多态等特性，通过简单的的方式和属性可以实现各种复杂操作，大大地提高了效率

Iterator

Iterator接口提供遍历任何Collection的接口，对Collection进行迭代的迭代器，我们可从一个Collection中使用迭代方法获取迭代器实例。Iterator取代了Java Collection Framework中的 Enumeration。Iterator与Enumeration主要有两点不一样：
1.迭代器允许调用者在迭代的过程中移除元素
2.迭代器的方法名有所改进
由于迭代实际上是描述集合中的位置的，所以这种依赖于位置的添加和移除元素的方法只有对自然有序的集合使用才有实际意义。

set

元素无序，不可重复，重复的元素会覆盖掉（注意：元素虽然是无序放入的，但是元素的位置是由Hashcode决定的，所以它的位置其实是固定的，加入到set的元素必须定义equals方法）
set只能用迭代器遍历，因为它是无序的，无法通过下标获取想要的值。

List

元素有序，可重复，可以通过索引来访问任何元素。

Map

存放的是<key,value>这样的键值对，它是一个将key映射到value的对象，Map中不能存在重复的key，每个key只能映射到一个value。

HashMap

存放的是<key,value>这样的键值对,
key不可以重复，Value可以重复；
key其实是Hashset，value是对应存放的；
key允许有一条记录为空，Value可以多条记录为空；

底层实现

在JDK1.6，1.7中HashMap采用位桶+链表实现，即使用链表处理冲突，即同一个hash值的元素在同一个链表里。但是当一个桶里的元素过多的时候，通过key依次查找效率就很低，所以JDK1.8对此作了改进。
在JDK1.8 中Hashmap采用位桶+链表+红黑树实现。当一个桶里的元素超过阈值（8）的时候，这个链表就转换成红黑树，这就大大减少了查找的时间。首先有一个数组，数组中的每一个元素都是链表（大概是这么个意思），当添加一个元素的时候，就先去计算这个key的Hash值，通过Hash值得到这个元素插入到数组的位置（位桶的位置），但是可能存在拥有同一个Hash值的元素已经在该位置上了，那么我们就把这个元素放到这个位置上的元素的后面，那么就形成了一个链表，显然同一个链表上的元素的key的hash值都相同。当链表的长度过长，也就是说数组同一个位置上的元素过多的时候，链表就会转换成红黑树，这样大大的提高了查找的效率。
JDK1.6和1.7：底层是 数组+链表 组成，我们可以设定一个默认的负载英子0.75，map在使用过程中不断的往里放数据，当数据量达到容量的0.75的时候，就进行扩容，要把原来的数组搬运到新的数组中去。
1.put方法：
判断数组是否需要初始化；
如果key为null，则放一个空值进去；
否则计算key的HashCode；
通过HashCode定位出元素应该插入的桶的位置；
如果桶的位置不为空，那么说明桶的位置有链表，那么久遍历判断里面的HashCode和key是不是和传入的相同；
如果相同，就覆盖；如果不同则插入到链表的下一个节点上；
如果桶的位置是空的，说明当前位置没有数据写入，就新增一个Entry对象写入当前位置。
注意：我们在调用addEntry写入Entry的时候，首先要判断是否要进行扩容，如果需要扩容，那么就要进行 2倍的扩容，并将当前的key重新计算HashCode并重新定位。
2.get方法：
计算当前的key的HashCode值，定位到对应的桶的位置；
判断这个位置是不是链表；
如果不是链表，根据key和hashCode是否相等来返回值；
如何是链表，就遍历链表，找到key和HashCode都相等时就返回值；
如果什么都没取到，就返回null；

JDK1.8 hashMap 采用 数组+链表+红黑树 实现，即当hash冲突严重的时候，同一个位桶 上的链表越来越长，这样在查询的时候效率就很低下，所以它增加了一个TREEIFY_THRESHOLD用来判断是否要转换成红黑数的阈值。HashEntry变成了node节点。
1.put方法：
当前桶是否为空，如果为空就初始化；
计算当前key的hashcode；
根据hashCode定位到具体的桶中，并且判断该位置的桶是否为空；
如果为空，则表示当前没有Hash冲突，当前位置没有数据写入，直接新建节点添加
如果不为空，说明当前桶处存在hash冲突，则判断当前桶的数据结构；
如果当前桶是一个红黑树，就要按照红黑数的方式写入数据；
如果当前桶是一个链表，那么就要将<key,value>封装成一个node节点，按链表的的方式处理hash冲突；
判断当前链表的长度是否超出阈值，如果超出就要转换成红黑树。
如果在遍历过程中找到key相同，则退出遍历；用新的值去覆盖原来的值；
判断是否要进行扩容；
2、get方法
计算当前key的hashCode，定位到所在的桶
如果桶的位置为空，则直接返回null；
否则判断桶的第一个位置的元素的key是否为查询的key；
如果是，则直接返回value；
如果不是则判断它的下一个是红黑树还是链表；
如果是红黑树，则按照树的方式查找；
如果是链表则进行链表的遍历，返回匹配的值；

HashMap如何解决散列冲突

JDK1.6和1.7中，使用链表解决hash冲突。在调用hashmap的get和put方法的时候，会首先调用hashCode的方法，去查找相关的key，当有冲突的时候，再去调用equals方法。当我们的键值对传递给put方法的时候，它调用key的HashCode方法来计算hashCode值，然后找到hash桶位置来存储对象，当获取对象时，我们通过key对象的equals方法找到正确的键值对，然后返回值对象。hashMap使用链表来解决碰撞问题，当碰撞发生的时候，对象会存储在链表的下一个节点上。当两个不同的键值却有相同的HashCode值的时候，也会存储在同一个桶位置的链表中，然后要通过键对象的equals（）来找键值对。
但是当一个桶里的元素过多的时候，通过key依次查找效率就很低，所以JDK1.8对此作了改进。
JDK1.8中增加了红黑树数据结构，当碰撞发生的时候，先判断当前桶位置的第一个位置的元素的key是不是要查找的key，如果是就直接返回，如果不是就去判断下一个节点是链表还是红黑树，如果是链表就按照链表的遍历去遍历这个链表，最后再去判断一下这个链表的长度是否超过了阈值，如果超过了就转换成红黑树。如果下一个节点是红黑树，那么久按照红黑树的遍历方式去遍历。

HashMap为什么是线程不安全的

并发先使用容易出现死循环，在hashmap扩容的时候回调用resize（）方法，就是这里的并发操作容易在一个桶上形成环形链表，这样当我们取一个不存在的key的时候，计算出的index刚好是这个环形链表的下标时，就会出现死循环。
循环链表的形成：在扩容过程中，当多个线程同时对这个HashMap进行put操作的时候，当察觉到hashMap的容量不够需要进行扩容，然后多个线程都会去执行resize（）操作，这个时候就会出现问题。首先hashMap进行扩容的时候，会将原来的数组拷贝到一个新的数组当中去，在新的数组中的链表会改变原先链表中元素的顺序，它会将元素从链表的头部插入，而环形链表就是在这个时候形成的。
当有两个线程同时扩容的时候：

线程二：读取hashmap，进行扩容

线程一：继续执行

这个过程为，先将A复制到新的hash表中，然后接着复制B到链头（A的前边：B.next=A），本来B.next=null，到此也就结束了（跟线程二一样的过程），但是，由于线程二扩容的原因，将B.next=A，所以，这里继续复制A，让A.next=B，由此，环形链表出现：B.next=A; A.next=B

HashMap的扩容机制

我们设置一个装载因子，默认是0.75，当hashmap中的元素个数超过数组大小的0.75时，就会进行扩容，也就是说，如果默认数组长度是16，那么当hashMap中的元素个数超过12时，就会把数组扩大到原来的2倍，即32,。然后重新计算每个元素的hash值，将原来的各个hash桶位置上的链表拷贝到新的hash表中。
至于为什么扩容要按照2的指数倍，因为在寻找桶的时候，会把hashCode与桶长度-1 进行 & 操作，如果长度是2的幂次时，len-1后面几位就是1，这时候与hash值进行& 运算的时候，hash值较低位更能够影响index的值，减少hash碰撞。若最后一位为0，那么hash值结尾为1或为0对index没有影响，容易放到一个桶里。

LinkedHashMap

LinkedHashMap是HashMap的子类，继承自Hashmap,它和hashmap不同的地方在于，它除了用hash表保存元素之外，还要维护一个记录元素是顺序的双向链表。这个顺序有两种，一，插入顺序（默认顺序）；二、访问顺序（每次访问的元素都会被插入到链表的尾部）。所以LinkedhashMap的初始化参数有3个，一个是默认长度，一个是装载因子，还有一个是boolean型的访问顺序。true就是按访问顺序排序，false就是按插入顺序排序。
LinkedHashMap按照插入顺序遍历的模式只对新插入的Entry有效，如果新插入的<key,value>对应的key已经存在，对应的entry在遍历顺序中的位置不会改变。

Treemap

对Key排好序的map，
key就是treeSet，value对应每一个key；
key要实现Comparable接口或treeMap自己的构造器（compartor）
key不能为null
它的实现算法是红黑树，在遍历时按照预先设定的排序算法有序的访问元素。
treeMap可以借助keyset和Entryset来进行访问。

HashTable和HashMap 的区别

HashTable现在基本已被淘汰，单线程转为使用HashMap，多线程使用ConcurrentHashMap。HashMap和HashTable都实现了map接口，存放的是<key,value>这样的键值对。HashTable的操作几乎和HashMap一致，主要的区别在于HashTable为了实现多线程安全，在几乎所有的方法上都加上了synchronized锁，而加锁的结果就是HashTable操作的效率十分低下。
hashMap没有排序
1）线程安全：
HashMap是线程不安全的类，多线程下会造成并发冲突，但单线程下运行效率较高；
HashTable是线程安全的类，很多方法都是用synchronized修饰，但同时因为加锁导致并发效率低下，单线程环境效率也十分低；

（2）插入null：
HashMap允许有一个键为null，允许多个值为null；
HashTable不允许键或值为null；

（3）容量：
HashMap底层数组长度必须为2的幂，这样做是为了hash准备，默认为16；
HashTable底层数组长度可以为任意值，这就造成了hash算法散射不均匀，容易造成hash冲突，默认为11；

（4）Hash映射：
HashMap的hash算法通过非常规设计，将底层table长度设计为2的幂，使用位与运算代替取模运算，减少运算消耗；
HashTable的hash算法首先使得hash值小于整型数最大值，再通过取模进行散射运算；

（5）扩容机制：
HashMap创建一个为原先2倍的数组，然后对原数组进行遍历以及rehash；
HashTable扩容将创建一个原长度2倍的数组，再使用头插法将链表进行反序；

（6）结构区别：
HashMap是由数组+链表形成，在JDK1.8之后链表长度大于8时转化为红黑树；
HashTable一直都是数组+链表；

（7）继承关系：
HashMap继承自AbstractMap类；
HashTable继承自Dictionary类；

（8）迭代器：
HashMap是fail-fast快速失败机制，也就是在迭代过程中修改集合结构，除非调用迭代器自身的remove方法，否则以其他任何方式修改都要抛出并发修改异常。如果想要迭代的时候修改map，可以使用concurrentHashMap。
而HashTable不是。

ConCurrentHashMap

hashMap的缺点：主要是多线程同时put的时候，如果触发了rehash操作，会导致HashMap中的链表中出现循环节点，这就会导致后面如果get的时候，可能会出现死循环。所以在并发的情况下不能使用hashMap，或者让hashmap同步，Collections.synchronizedMap(hahsMap)；
HashTable的缺点：虽然它是同步的，使用synchronized来保证线程安全，但是在线程竞争激烈的情况下HashTable的效率非常低下。因为当一个线程访问HashTable的同步方法时，有其他的线程访问hashTable的同步方法时，可能会进入到阻塞或轮询状态。比如线程A使用put来添加元素，线程B不但不能使用put方法来添加元素，也不能使用get方法来获取元素，所以竞争越大效率越低。
hashTable容器在竞争激烈的并发环境下效率低下的原因在于，所有访问HashTable的线程必须竞争同一把锁，而ConCurrentHashMap，它的原理是分段锁，首先将数据分成一段一段的存储，然后给每一段数据配一把锁，当一个线程占用锁访问其中一个段数据的时候，其他段的数据也能被其他的线程访问。
ConcurrentHashMap是由Segment数组结构和HashEntry数组结构组成。Segment实际继承自可重入锁（ReentrantLock），在ConcurrentHashMap里扮演锁的角色；HashEntry则用于存储键值对数据。一个ConcurrentHashMap里包含一个Segment数组，每个Segment里包含一个HashEntry数组，我们称之为table，每个HashEntry是一个链表结构的元素。

初始化构造函数传入了三个参数：
initialCapacity：初始容量大小 ，默认16。
loadFactor： 装载因子，默认0.75，当一个Segment存储的元素数量大于initialCapacity* loadFactor时，该Segment会进行一次扩容。
concurrencyLevel ：并发度，默认16。并发度可以理解为程序运行时能够同时更新ConccurentHashMap且不产生锁竞争的最大线程数，实际上就是ConcurrentHashMap中的分段锁个数，即Segment[]的数组长度。如果并发度设置的过小，会带来严重的锁竞争问题；如果并发度设置的过大，原本位于同一个Segment内的访问会扩散到不同的Segment中，CPU cache命中率会下降，从而引起程序性能下降。通常我们把segment的长度设置为大于等于concurrencyLevel 的第一个2的n次方的数。
put操作
定位segment：取得key的hashcode值进行一次再散列（通过Wang/Jenkins算法），拿到再散列值后，以再散列值的高位进行取模得到当前元素在哪个segment上。
就是说，我们计算出key的hash值，将hash值向右移动segmentShift位，等到hash值的高位；将这个高位再与segmentMark做 & 运算，就得到segment的索引了。
定位table：同样是取得key的hash值以后，用hash值的全部 和 table的长度进行-1 &操作，得到当前元素在table的哪个元素上。然后往里面放值
get操作
定位segment和定位table后，依次扫描这个table元素下的的链表，要么找到元素，要么返回null。
在高并发下的情况下如何保证取得的元素是最新的？
答：用于存储键值对数据的HashEntry，在设计上它的成员变量value等都是volatile类型的，这样就保证别的线程对value值的修改，get方法可以马上看到。
put()方法

1、首先定位segment，当这个segment在map初始化后，还为null，由ensureSegment方法负责填充这个segment。

1.1对Segment 加锁
1.2定位所在的table元素，并扫描table下的链表
找到的时候：put操作会覆盖掉原来的值，而putAbsent不会覆盖掉原来的值，它会中断循环，返回原来的值给调用者。
找不到时：采用头插法将新元素插入到链表的头
1.3检查是否要扩容，如果需要扩容，则segment是不会进行扩容的，扩容的是segment下的table数组，每次都是将数组翻倍
JDK1.8直接采用Node数组+链表+红黑树来实现，并发控制使用Synchronized和CAS来操作，类似于对线程安全的hashMap的优化

put操作，对当前的table进行无条件自循环直到put成功：
1.如果没有初始化就先调用initTable（）方法来进行初始化过程
2.如果没有hash冲突就直接CAS插入
3.如果还在进行扩容操作就先进行扩容
4.如果存在hash冲突，就加锁来保证线程安全，这里有两种情况，一种是链表形式就直接遍历到尾端插入，一种是红黑树就按照红黑树结构插入，
最后一个如果该链表的数量大于阈值8，就要先转换成黑红树的结构，break再一次进入循环
5.如果添加成功就调用addCount（）方法统计size，并且检查是否需要扩容
扩容： 这里主要涉及到多线程并发扩容,ForwardingNode的作用就是支持扩容操作，将已处理的节点和空节点置为ForwardingNode，并发处理时多个线程经过ForwardingNode就表示已经遍历了，就往后遍历。
put流程中在并发处理中使用的是乐观锁，当有冲突的时候才进行并发处理。
get操作
1.计算hash值，定位到该table索引位置，如果是首节点符合就返回
2.如果遇到扩容的时候，会调用标志正在扩容节点ForwardingNode的find方法，查找该节点，匹配就返回
3.以上都不符合的话，就往下遍历节点，匹配就返回，否则最后就返回null

弱一致性

get和containskey都是通过遍历链表来判断是否存在相同的key，但是由于遍历过程中可能有其他的线程对链表的结构做了调整，因此他们返回的数据可能是过时的数据，这一点就是Concurrenthashmap的弱一致性的体现。

HashSet

基于散列表的集合，它只在某个桶中查找元素，而不会去查看集合中的所有元素。由于散列是分散在表的各个位置上的，所以访问它的顺序是随机的。后台是一个HashMap，只不过生成一个HashSet的话，系统只提供key的访问，如果两个key重复，那么后面的key会覆盖之前的key。HashSet采用hashCode算法来存取集合中的元素，因此具有比较好的读取和查找性能。
HashSet是基于HashMap实现的，底层采用的是HashMap来保存数据，所有写入HashSet的元素其实都是由HashMap的key来保存的，而HashMap的Value则存储了一个静态的object对象（向上转型，这样value就可以是任何类型的值了）。HashSet绝大部分方法都是通过调用HashMap的方法来实现的，因此HashSet和HashMap两个集合在本质上是相同的。
它是这样判断元素的重复的：通过equals和HashCode来判断两个元素是不是相等，如果两个元素通过equals为true，并且两个元素的HashCode也相等，那么这两个元素就是相等的，所以要保存在HashSet中的对象的equals和hashcode方法都要重写。

LinkedHashSet

是Hashset的一个子类，它和HashSet的不同之处在于，它还维护着一个双重链表，这个链表记录元素的顺序，遍历的时候只需要按照链表来访问元素，它维护元素的插入顺序的性质其实是继承自LinkedHashMap，所以它存储的元素是有序的。我们在进行插入的时候既要计算元素的hashcode又要维护链表。

TreeSet

是实现了SortSet接口，是一种排序的set集合，底层是TreeMap本质上是一个红黑树原理。TreeSet的排序分成两类，一、自然排序；二定制排序
自然排序：调用了CompareTo方法比较元素大小，然后按照升序排序，所以自然排序中的元素必须实现Comparable接口，否则会抛出异常，如果CompareTo方法返回0则说明两个元素相等
定制排序：在集合中写排序规则，定制排序需要关联一个comparator对象，由Comparator提供排序逻辑。

EnumSet

专门为枚举类型设计的集合，因此集合元素必须是枚举类型

总结：
hashSet和treeSet是set集合中用的最多的集合，HashSet总是比Treeset性能好，因为HashSet不需要额外维护元素的顺序
LinkedHashSet需要额外的链表来维护元素的插入顺序，因此在插入时的性能要比Hashset 低，但是在迭代访问的时候性能更高，因为插入的时候既要计算hashCode又要维护链表，而遍历的时候只需要按链表来访问元素。
EnumSet是所有set元素中性能最好的，但是它只能保存Enum类型的元素。

ArrayList，LinkedList，Vector

LinkedList：双向链表实现，增删快，查询慢，线程不安全
ArrayList：数组实现，查询快，增删慢，是线程不安全的
Vector：数组实现，底层是Object数组，是线程安全的

ArrayList和LinkedList比较：

1.都是不同步的，也就是说他们都说线程不安全的
2.ArrayList底层是Object数组，LinkedList底层是一个双向链表
3.ArrayList采用数组存储，所以插入和删除时间复杂度受位置影响，但LinkedList采用链表存储数据，所以不受位置影响
4.ArrayList支持随机访问，LinkedList不支持随机访问
5.内存空间占用，ArrayList空间浪费体现在列表结尾会预留一定的容量空间，LinkedList的空间浪费体现在他的每一个元素除了元素本身的值还要存储他的直接后继和前驱。
6.自动扩容：ArrayList初始大小是0，然后当add第一个元素的时候，他的大小就变成了10，并且后续继续扩容的时候会变成当前大小的1.5倍；LinkedList是一个双向链表，没有初始化大小，也没有扩容机制，就是一直在后面或者前面新增就好了。
由于LinkedList不做任何位置信息的缓存，所以list.get(i)每次都是从头开始遍历链表，效率低下。

ArrayList和Vector的比较：

1.底层都是用数组实现
2、Vector是线程安全的，ArrayList不是线程安全的；Vector类中有很多方法都是用Synchronized修饰的，这就导致了Vector在效率上比ArrayList低很多
3、两个都是采用线性的连续空间存储数据，但是当空间充裕的时候，两个类的增加方式是不一样的
4、Vector可以设置增长因子，但是ArrayList就不可以。我们往一个Vector或ArrayList里插入一个元素的时候，如果内部数组空间不够，那么他们俩都会扩展它们的空间大小，Vector默认是增长一倍，而ArrayList是增加1/2。

ArrayList自动扩充机制

实现ArrayList.ensureCapacity(int minCapacity)
获得当前elementData的属性长度oldCapacity，比较oldCapacity和minCapacity，如果oldCapacity < minCapacity就对当前的List进行扩容。策略：取（oldCapacity *3）/2+1和minCapacity中更大的那个。然后使用数组拷贝的方法，把以前存放的数据转移到行的数组对象中；否则不扩容。

Collection和Collections的区别

Collection是接口，他是集合类的上级接口
Collections是类，它是集合类的一个帮助类，，提供了操作集合的工具方法，对各种集合的搜索，排序，线程安全等操作。

Comparable和Comparator接口的区别

Comparable是java.lang包下的接口； Comparator是java.util包下的接口
Comparable提供自然排序，String，Integer等都实现了这个接口。我们的Arrays或者Collections的排序方法对对象进行排序的时候，就需要在自定义类中实现Comparable接口并重写CompareTo方法；
Comparator是一个外部比较器，提供定制排序，当对象的自然排序不能够满足我们的要求的时候，我们就可以定制自己的比较器来完成两个对象之间的比较大小，使用Comparator是策略模式，就是它并不会改变对象自身，而是用一个策略对象来改变它的行为。