java容器

equals和hashCode

• equals和hashcode间的关系：
  • 如果两个对象相同（即equals比较返回true），那么他们的hashcode一定要相等。
  • 如果他们的hashcode相等，他们的equals不一定相等。
• hash算法（散列算法）：
  • 对象数据根据该对象的特征使用特定的算法将其定义到一个地址上，那么后面进来的数据只要看对应的hashcode地址上是否有值，没有的话就直接插入，有的话不进行任何操作，这样就大大减少了equals的比较次数（因为两个不同的对象其hash也可能是相等的，所有还是需要进行equals的比较的，这样效率就大大提高了。

List

• List 是有序的 Collection。Java List 一共三个实现类：分别是ArrayList、Vector 和 LinkedList。
• ArrayList（数组）
  • 内部数组实现
  • 优点：快速访问和随机查找
  • 缺点：当从 ArrayList 的中间位置插入或者删除元素时，需要对数组进行复制、移动、代价比较高。因此，它适合随机查找和遍历，不适合插入和删除。
• Vector
  • 内部数组实现
  • 优点：线程同步
  • 缺点：访问它比访问 ArrayList 慢
• LinkList（链表）
  • 内部双向链表实现
  • 优点：很适合数据的动态插入和删除。专门用于操作表头和表尾元素，可以当作堆栈、队列和双向队列使用。
  • 缺点：随机访问和遍历速度比较慢
    高了。

Set

• Set 注重独一无二的性质,该体系集合用于存储无序(存入和取出的顺序不一定相同)元素，值不能重复。对象的相等性本质是对象 hashCode 值（java 是依据对象的内存地址计算出的此序号）判断的，如果想要让两个不同的对象视为相等的，就必须覆盖 Object 的 hashCode 方法和 equals 方法。
• HashSet（Hash 表）
  • 存放的是哈希值
  • HashSet 首先判断两个元素的哈希值，如果哈希值一样，接着会比较equals 方法 如果 equals 结果为 true ，HashSet 就视为同一个元素。如果 equals 为 false 就不是同一个元素。
  • HashSet 通过 hashCode 值来确定元素在内存中的位置。一个 hashCode 位置上可以存放多个元素。
• TreeSet（二叉树）
  • 使用二叉树的原理对新 add()的对象按照指定的顺序排序（升序、降序），每增加一个对象都会进行排序。
  • Integer 和 String 对象都可以进行默认的 TreeSet 排序，而自定义类的对象是不可以的，自己定义的类必须实现 Comparable 接口，并且覆写相应的 compareTo()函数，才可以正常使用。
• LinkHashSet（HashSet+LinkedHashMap）

Map

• HashMap（数组+链表+红黑树）
  • 只允许一条记录的键为 null，允许多条记录的值为 null。
  • 非线程安全

• Java 7的实现

  
  image.png
  

  大方向上，HashMap 里面是一个数组，然后数组中每个元素是一个单向链表。上图中，每个绿色的实体是嵌套类 Entry 的实例，Entry 包含四个属性：key, value, hash 值和用于单向链表的 next。

• JAVA8 实现（加入红黑树）
  • 当链表中的元素超过了 8 个以后，会将链表转换为红黑树。
• ConcurrentHashMap
• ConcurrentHashMap 是一个 Segment 数组，Segment 通过继承ReentrantLock 来进行加锁，所以每次需要加锁的操作锁住的是一个 segment
• HashTable（线程安全）
  • 承自 Dictionary 类
  • 不允许null为健，null为值。
• TreeMap（可排序）
  • 在使用 TreeMap 时，key 必须实现 Comparable 接口或者在构造 TreeMap 传入自定义的Comparator，否则会在运行时抛出 java.lang.ClassCastException 类型的异常。
• LinkHashMap（记录插入顺序）