Java集合

ArrayList与LinkedList

• ArrayList：能够自动增长容量的数组，搜索，读取数据的时候效率较高。
• LinkedList：是一个双向的链表，添加，和删除数据的时候效率较高。

List

• ArrayList
  • 底层数据结构是数组，线程不安全。
  • ArrayList是基于动态数组实现的，在增删的时候，需要数组的拷贝复制。
  • ArrayList的默认初始化容量是10，每次扩充的时候增加原先容量的一半，也就是原来的1.5倍。
  • 删除元素的时候，不会减少容量，若希望减少容量，则需要调用trimToSize()。
  • 它不是线程安全的，它能存放null值。
• LinkedList
  • 底层数据结构是链表，线程不安全。
• Vector
  • 底层数据结构是数组，现场安全。

Map

• HashMap
  • 在JDK8中，HashMap的底层是：数组+链表（散列表）+红黑树。
  • 在散列表中有装载因子这个属性，当 装载因子*初始化容量 小于散列表元素的时候，该散列表会在散列，扩容2倍。
  • 装载因子默认是0.75。
  • 装载因子过大，可以减少散列表的在散列（扩展），但同时会导致散列表冲突的可能性变大（散列冲突也是耗性能的一个操作，要得操作链表（红黑树））
  • 装载因子过小，可以减少散列冲突的可能，但同时扩容的次数就会变的很大多。
  • 初始容量的默认值是16。
  • 初始量过大，那么遍历的速度就会被影响。
  • 初始量过小，散列在散列（扩容）次数就会变多，扩容也是一件非常耗费性能的一件事。
  • HashMap并不是直接拿key的哈希值来用的，它会将key的哈希值的高16为进行异或操作，这样就使得将元素放入哈希表的时候增加了一定的随机性。
  • 注意：并不是桶上有8位元素的时候它就变成了红黑树，它的同时满足散列表的容量大于64才可以。
• LinkedHashMap
  • LinkedHashMap底层是散列表和双向链表。
• TreeMap
  • TreeMap的底层是红黑树。

Set

• Set
  • 底层就是Map。
• HashSet
  • 无序，允许为null，底层是HashMap（散列表+红黑树），非线性同步。
• TreeSet
  • 有序，不允许为null，底层是TreeMap（红黑树），非线性同步。
• LinkedHashSet
  • 迭代有序，允许为null，底层是HashMap+双向链表，非线性同步。

面试题目

• Java中HashMap的key值要是为类对象则该类需要满足什么条件？
  • 需要同时重写该类的hashCode()方法和它的equals()方法。
  • 在插入元素的时候是先算出该对象的hashCode。如果hashcode相等话的。那么表明该对象是存储在同一个位置上的。
  • 如果调用equals()方法，两个key相同，则替换元素。
  • 如果调用equals()方法，两个key不相同，则说明该hashCode仅仅是碰巧相同，此时是散列冲突，将新增的元素放在桶子上。
  • 只要两个对象的成员变量的值是相等的，那么我们就认为这两个对象是相等的。
  • 重写了equals()方法，就要重写hashCode()的方法。因为equals()认定了这两个对象相同，而同一个对象调用hashCode()方法时，是应该返回相同的值的！