Collection体系原理了解

2019-07-22 本文已影响0人 DeeJay_Y

Collection体系简介

有序无序意味着存在索引且从0开始

Collection体系提供的常用方法
- new: new ArrayList(Collection), new ArrayList()
- R: size()/ isEmpty()/ contains() / for() / stream()
- C/U: add()/ addAll()/ retainAll()
- D: clear()/ remove()/ removeAll()

不允许有重复元素的集合
- 判断重复调用的是equals()
如果要自己实现一个Set，怎么实现?
1.如果要自己实现一个Set，肯定能想到的是一个简单思路就是每次添加新元素时，查看现有的元素中存不存在目标元素，如果有则不加入。这样的思路的问题是，如果现有的元素已经有很多了的话，那么会比较很多次，性能会受影响。
2.所以举个例子：假设我们要把所有用户的姓名加入到一个自己实现的Set中来时，我们可以先根据用户的姓来进行比较添加，比如现有赵钱孙李四种姓氏，要添加赵四时，就只需要去跟赵姓中的元素们进行比较，如有相同则不添加，不需要跟整个现有集合进行比较。提高了性能。
3.上述的例子，就是hashCode的含义，对于Set集合，将Object们对应为一个个的int值，相同的int值对应的就相当于是一个姓氏，新加Object时，就只需要跟相同int值的Object们进行equals比较就好了。而这个将Object对应为int值的方法，就是hashCode()

上述的一个个int值对应的小集合，称为hash桶

Java世界里的又一重要约定: hashCode
- 同一个对象必须始终返回相同的hashCode
- 两个对象的equals返回true，必须返回相同的hashCode
- 两个对象不等，也可能返回相同的hashCode

关于keySet()，返回的是一个包含所有key的set，任何对这个set的修改都会反映到原先的Map上，反之亦然，切记！！

最常用，最高效的Map实现
常见面试题：
- HashMap的扩容（resize()方法，本质思路还是一样的，创建一个更大的HashMap）
- HashMap的线程不安全性（使用ConcurentHashMap）
- HashMap在Java7+后的改变：链表 -> 红黑树
  是为了防止大量对象的hashCode值一样导致性能下降改变的。
HashMap和HashSet在本质上其实是一种东西

HashMap的key就是一个HashSet

和LinkedHashSet不同的是，TreeSet会对内部的元素进行一次默认的排序，而不是仅仅按照插入的顺序存储。
另外TreeSet其内部结构是一个二叉树，可以把查找的算法复杂度从o(n)下降到o(logn)（和ArrayList对比）。