1、面试题 - 集合和数组的区别？
数组的特点：
? ? ? ? 1.数组中存放的元素类型一致
? ? ? ? 2.数组的长度一经定义后无法进行修改
集合的特点：
? ? ? ? 1.集合中可以存放任意类型的数据
? ? ? ? 2.集合没有长度的限制
2、List接口总结
List接口
1.有序（存取顺序一致）
2.允许存储重复元素
3.允许存储null值
实现类
1.ArrayList
? ? ? ? -1.1基于数组的数据结构实现
? ? ? ? -1.2查询快，增删慢
? ? ? ? -1.3线程不安全，建议单线程使用
2.LinkedList
? ? ? ? -2.1基于链表的数据结构实现
? ? ? ? -2.2查询慢，增删快
? ? ? ? -2.3线程不安全
3.Vector
? ? ? ? -3.1线程安全
? ? ? ? -3.2API方法中，都带有synchronize关键字
? ? ? ? -3.3效率低
4.CopyOnWriterArrayList
? ? ? ? -4.1线程安全
? ? ? ? -4.2ReentrantLock 可重入锁
? ? ? ? -4.3多线程并发访问下，效率高
3、Set接口总结（HashSet）
Set 接口
* 1.存取无序
* 2.不允许添加重复元素
*
* HashSet
* 1.JDK1.8 前后数据结构有啥不同
* - 1.1 JDK1.8之前 "数组+链表"
* - 1.2 JDK1.8之后 "数组+链表+红黑树"
* 2.存取无序
* 3.不允许添加重复元素 ， 依据equals()和hashcode()
* 4.线程不安全
* 5.允许存放null值
*
* 思考：
* 1.HashSet 怎么出现无序的情况的？
* 底层计算hash值时，通过(key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);计算
* 计算对应添加元素的的“桶”数组的下标，通过(n - 1) & hash计算。
*
* 2.HashSet 如何保证元素的唯一性？
* 根据hashcode()和equals()保证元素的唯一性。
* 当hashcode一致时，equals不一定一致，需要查看equals是否一致，
* 若equals一致，则认定为相同元素；
* 若equals不一致，则认定为不同元素；
* 当equals一致时，hashcode一定一致，直接认定是相同元素。
*
* 3.JDK8版本前后，底层存储结构有什么不同？为什么做出改变？
* 1).底层是由数组 - 链表组成，当添加新元素时，它会根据元素的hash值找到对应的"桶"，也就是HashMap源码中Node<K, V> 里的元素，
* 并插入到对应位置的链表中，链表元素个数过长时会转化为红黑树(JDK1.8后的版本)。
* 2).链表取元素是从头结点一直遍历到对应的结点，这个过程的复杂度是O(N) ，而红黑树基于二叉树的结构，查找元素的复杂度为O(logN) ，
* 所以，当元素个数过多时，用红黑树存储可以提高搜索的效率。
*
* 4.既然红黑树的效率高，那怎么不一开始就用红黑树存储呢？
* 红黑树虽然查询效率比链表高，但是结点占用的空间大，只有达到一定的数目才有树化的意义，这是基于时间和空间的平衡考虑。
* 此处翻译源代码注释：单个 TreeNode 需要占用的空间大约是普通Node的两倍，所以只有当包含足够多的Nodes时才会转成 TreeNodes，
* 这个足够多的标准就是由 TREEIFY_THRESHOLD 的值（默认值8）决定的。而当桶中节点数由于移除或者 resize (扩容) 变少后，
* 红黑树会转变为普通的链表，这个阈值是 UNTREEIFY_THRESHOLD（默认值6）。
*
* 5.为什么树化标准是8个？
* 此处翻译源代码注释：如果hashCode的分布离散良好的话，那么红黑树是很少会被用到的，因为各个值都均匀分布，很少出现链表很长的情况。
* 在理想情况下，链表长度符合“泊松分布”，各个长度的命中概率依次递减，注释中给我们展示了1-8长度的具体命中概率，当长度为8的时候，
* 概率概率仅为0.00000006，这么小的概率，HashMap的红黑树转换几乎不会发生，因为我们日常使用不会存储那么多的数据。
* 若用户使用HashMap过程导致hashCode分布离散很差的场景（思考一下是什么场景），这个时候再转换为红黑树就是一种很好的退让策略。
* 可以避免查询效率低下的问题，从而有效防止用户自己实现了不好的哈希算法时导致链表过长的情况。
*
* 6.底层计算hash值时，为什么要(key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);这样运算？
* 传入key之后，hash()会获取key的hashCode进行无符号右移 16 位，然后进行按位异或，并把运算后的值返回，这个值就是key的哈希值。
* 这样运算是为了减少碰撞冲突，因为大部分元素的hashCode在低位是相同的，不做处理的话很容易造成冲突。
*
* 7.如何计算对应添加元素的的“桶”数组的下标？
* tab[i = (n - 1) & hash]) 当查找不到对应的索引时，就会新建一个新的结点作为链表的头结点。
* 通过位运算，在每次扩容时都不用重新计算hash，省去了不少时间，而且新增有效位是0还是1是带有随机性的，
* 之前两个碰撞的Entry又有可能在扩容时再次均匀地散布开，达到较好的分布离散效果。
*
* 8.为什么退化为链表的阈值是6？
* 当链表长度达到阈值8的时候会转为红黑树，但是红黑树退化为链表的阈值却是6。主要是一个过渡，避免链表和红黑树之间频繁的转换。
* 如果阈值是7的话，删除一个元素红黑树就必须退化为链表，增加一个元素就必须树化，来回不断的转换结构无疑会降低性能，
* 所以阈值才不设置的那么临界。
?4.Set接口总结
* Set 接口
* 1.存取无序
* 2.不允许添加重复元素
*
* HashSet
* 1.JDK1.8 前后数据结构有啥不同
* - 1.1 JDK1.8之前 "数组+链表"
* - 1.2 JDK1.8之后 "数组+链表+红黑树"
* 2.存取无序
* 3.不允许添加重复元素 ， 依据equals()和hashcode()
* 4.线程不安全
* 5.允许存放null值
*
* TreeSet
* 1.基于红黑树数据结构实现
* 2.添加进来的元素会进行排序
* - 2.1 元素自身具备比较性 implements Comparable 重写compareTo(o1)
* - 2.2 容器具备比较性 new Comparator 重写compare(o1,o2)
* 3.不允许添加重复元素 ， 依据compareTo(o1)或compare(o1,o2)的返回值
* 4.线程不安全
* 5.不允许存放null值
*
* LinkedHashSet
* 1.JDK1.8 前后数据结构有啥不同
* 2.存取有序，依靠链表实现存取有序
* 3.不允许添加重复元素 ， 依据equals()和hashcode()
* 4.线程不安全
* 5.允许存放null值
*
* CopyOnWriteArraySet
* 线程安全 ， 利用可重入锁ReentrantLock
?
4.Map总结
Map Interface接口 Map<K,V>键值对
* 1.put(K key, V value)
* 2.V get(Object key)
* 3.Set<Map.Entry<K,V>> entrySet() 获取每一个元素的键值对key-value
* Set<K> keySet() 获取所有元素键Key的集合
* Collection<V> values() 获取所有元素值Value的集合
*
* HashMap
* 1.<key,value> key-->HashSet
* 2.键的特点
* - 2.1 不允许重复存放键
* - 2.2 不能保障存储顺序
* - 2.3 允许存放null键
* 3.值的特点
* - 3.1 一旦键重复存放，覆盖对应的值
* - 3.2 允许重复存放值
* - 3.3 允许存放null值
* 4.线程不安全
*
* TreeMap
* 1.<key,value> key-->TreeSet
* 2.键的特点
* - 2.1 不允许重复存放键
* - 2.2 键会进行排序（要么键的元素具备比较性，要么TreeMap容器具备比较性）
* - 2.3 不允许存放null键
* 3.值的特点
* - 3.1 一旦键重复存放，覆盖对应的值
* - 3.2 允许重复存放值
* - 3.3 允许存放null值
* 4.线程不安全
*
* LinkedHashMap
* 1.<key,value> key-->LinkedHashSet
* 2.参考HashMap，但是LinkedHashMap可以确保键key存取是有序的
* 3.线程不安全
*
* HashTable
* 1.JDK1.0
* 2.线程安全
* 3.synchronized 关键字
* 4.效率较低
*
* Properties
* 1.extends Hashtable
* 2.对properties的属性文件进行操作
*
* ConcurrentHashMap
* 1.JUC并发包
* 2.线程安全
?
|