image.png

Collection集合

  1. // 交集：C = A ∩ B
  2. // 并集：A U B = B U A
  3. Collection coll<T> = new ArrayList<T>();
  4. // 创建collection
  5. boolean add(Object obj)
  6. // 添加元素到当前集合中
  7. boolean addAll(Collection<?> c);
  8. // 将c集合中的所有元素添加到当前集合中
  9. boolean remove(Object obj);
  10. // 删除集合中找到的第一个与obj对象equals的元素，返回true
  11. boolean removeAll(Collection<?> c);
  12. // 删除与coll集合相同的元素
  13. void retainAll(Collection<?> c);
  14. // 从集合中删除不包含c集合中的元素
  15. boolean isEmpty();
  16. // 判断当前集合是否为空集合
  17. boolean contains(Object obj);
  18. // 判断当前集合是否存在与obj对象equals的元素
  19. boolean containsAll(Collection<?> c);
  20. // 判断c集合中元素是否都在当前集合中
  21. int size();
  22. // 获取当前元素集合中的实际存储的元素数量
  23. boolean retainAll(Collection<?> c);
  24. // 当前集合变成与c交集的元素 (coll=coll ∩ c)
  25. Object[] toArray();
  26. // 返回包含当前集合中所有元素的数组
  27. void clear();
  28. // 清空集合
  29. Iterator iterator();
  30. // 返回一个迭代器

Collections

Collections后面有多了一个s 它是一个操作Set、List、Map等集合的工具类，提供了一系列静态方法对集合进行排序、查找修改等操作 提供了对集合对象设置不可变、对集合对象实现同步控制等方法

  1. boolean addAll(Collection<?super T>c, t...elements);
  2. // 将所有指定元素添加到指定collection中
  3. int binarySearch(List<?extends Comparable<?super T>>list, key);
  4. // 寻找元素下标，List是可比较大小的，List是有序的
  5. int binarySearch(List<?extends T>list, T key, Comparator<?super T>c);
  6. // 寻找元素下标，List按照C比较器规则排序过的数组进行寻找
  7. T max(Collection<?extends T> coll);
  8. // 在集合coll中寻找最大值
  9. void reverse(List<?>list);
  10. // 反转指定列表List中 元素的 顺序
  11. void shuffle(List<?>list);
  12. // List集合元素进行随机排序
  13. void sort(List<T> list);
  14. // 自然顺序升序
  15. void sort(List<T>list, Comparator<?super T>c);
  16. // 根据Comparator产生的顺序对List集合进行排序
  17. void swap(List<?>list, int i, int j);
  18. // 交换list集合中i和j索引位置的元素
  19. int frequency(Collection<?>c, T o);
  20. // 返回集合c，o出现的次数
  21. void copy(List<?super T>dest, List<? extends T>src);
  22. // 将src的元素复制到dest中
  23. boolean replaceAll(List<T>list, T oldVal, T newVal);
  24. // 使用newVal替换所有oldVal
  26. // Collection类提供了多个synchronizedXxx()方法
  27. // 该方法可使将指定集合包装成线程同步的集合
  28. // 从而可以解决多线程并发访问集合时的线程安全问题
  30. // Collections类中提供了多个unmodifiableXxx()方法
  31. // 该方法返回指定的集合是不可修改的视图。

Iterator->迭代器

image.png

  1. Collection<Integer> c = new ArrayList<>();
  2. c.add(1);c.add(2);c.add(3);c.add(4);c.add(5);
  4. // 迭代器获取
  5. Iterator<Integer> it = c.iterator();
  6. while(it.hasNext())
  7.     System.out.println(it.next());
  9. E next();
  10. // 返回迭代的下一个元素
  11. boolean hasNext();
  12. // 如果有元素可以迭代，返回true
  13. void reomve();
  14. // 通过迭代器删除元素

foreach

foreach它是在jdk5后出现的 foreach底层实现实际上就是普通的for循环实现的 foreach遍历集合的实现也是一个迭代器

  1. // 遍历数组
  2. a = {1,2,3};
  3. for(int i: a)
  4.     System.out.println(i);
  6. // 遍历集合
  7. Collection<Integer> c = new ArrayList<>();
  8. c.add(1);c.add(2);c.add(3);c.add(4);c.add(5);
  9. for(Integer i: c)
  10.     System.out.println(i);

Iterable自定义迭代器

List集合

List的特点：

  • List继承自Collection可以使用Collection相关方法
  • 新增了一些根据元素索引来操作集合的特有方法
  • 线性存储，带索引有序的集合，有重复的元素
  • 遍历效率快，增删效率慢

ArrayList

ArrayList底层使用数组存储结构，所以查询快，增删慢

可变长数组的原理：

  • jdk8中，默认初始容量为0，
  • 在首次添加一个元素时初始化容量为10
  • 每次添加修改modCount属性值
  • 每次添加元素都会查询容量是否足够，当容量不足时进行扩容，扩容大小为原容量的1.5倍(size+(size>>1))
  1. // List继承了Collection接口中的方法
  2. List<E> list = new ArrayList<>();
  3. // list创建
  4. void add(int index, Object obj);
  5. // 往指定位置添加
  6. boolean addAll(int index, Collection cDF);
  7. // 将c集合添加到指定位置
  8. E remove(int index);
  9. // 弹出指定位置的元素(删除并返回)
  10. E set(int index, E ele);
  11. // 弹出指定位置的元素并使用ele进行替换
  13. E get(int index);
  14. // 获取指定位置的元素
  15. List subList(int from, int end);
  16. // 返回List从[from, end)的元素
  17. int indexOf(Object obj);
  18. // 返回obj的位置，没有返回-1
  19. int lastIndexOf(Object obj);
  20. // 返回obj最后一次的位置，没有返回-1

ListIterator

List特有的迭代器

  1. ListIterator<E> List.listIterator();
  2. // 创建迭代器
  3. ListIterator<E> List.listIterator(int index);
  4. // 从指定位置开始创建,[index, size())
  6. void add();
  7. // 添加元素到对应集合
  8. void set(E obj);
  9. // 替换正迭代的元素
  10. void remove();
  11. // 删除刚迭代的元素
  12. boolean hasPrevious();
  13. // 逆向遍历，后方是否还有元素
  14. E previous();
  15. // 返回列表中前一个元素
  16. int previousIndex();
  17. // 返回列表中前一个元素的索引
  18. int nextIndex();
  19. // 返回下一个索引
  20. boolean hasNext(); E next();
  21. // 继承原迭代器

LinkedList

  • 继承对象：AbstractSequentialList 类
  • 实现接口：
    • Queue接口：可作为队列使用
    • List接口：可进行列表相关操作
    • Deque接口：可作为队列使用
    • Cloneable接口

LinkedList是List接口的常用实现类 LinkedList底层存储数据使用（双向链表） 特点增删快，查询慢 可以实现双端队列、队列、栈

  1. // 链表
  2. LinkedList list = new LinkedList();
  3. V indexOf(V v); // 获取索引位
  4. V set(int index, V v); // 更新指定位置元素
  5. V remove(int index); // 删除索引元素
  7. // 队列
  8. Queue queue = new LinkedList();
  9. void addFirst(V V); // 首部入队
  10. void addLast(V V); // 尾部入队
  11. V getFirst(); // 首部读取
  12. V getLast(); // 尾部读取
  13. V removeFirst(); // 首部弹出
  14. V removeLast(); // 尾部弹出
  15. V peek(); // 只获取不出队
  16. V poll(); // 弹出最早进入的元素
  18. // 栈
  19. Stack stack = new Stack<>();
  20. void push(V V); // 压栈
  21. V pop(); // 弹栈
  23. // 堆
  24. Priority minheap = new PriorityQueue(); // 最小堆
  25. add(V v) offer(V v); // 压入
  26. remove() poll(); // 弹出

Vector

Stack

它是栈结构

Set集合

Set接口是Collection的子接口，但比collection接口更加严格 set集合不允许有相同元素(引用类型要注意) 如果添加相同元素则忽略重复元素

set判断重复的方法是用equals进行判断的， 当this.equals(obj)返回true时，这个元素就是重复的

HashSet

HashSet底层以数组+链表的形式进行存储的 HashSet集合判断两个元素相等的标准 存储无序的

  1. boolean add();
  2. // 添加，存在返回false
  3. boolean contains();
  4. // 是否存在,存在返回true
  5. boolean remove();
  6. // 删除，成功返回true
  7. int size();
  8. // 返回元素数量
  10. // 迭代
  11. for(E e: set)
  12.     print(e);

LinkedHashSet

存储有序的，它在HashSet的基础行，在节点中新增两个属性before和after维护了节点的前后添加顺序 性能略低于HashSet

SortedSet

有序集合

TreeSet

二叉树，实现了自动排序功能 底层使用平衡二叉树 查询效率高于链表

TreeSet存取元规则 存储元素时根据当前加入与已有元素比较的结果决定元素加入的位置 结果负数时放左边，结果为正时放右边，结果为0时则覆盖

List和set的各接口的特征和特点

  • List：接口，元素可重复，有序（存取顺序一致）
    • ArrayList：底层结构为数组，查询快，增删慢，线程不安全
    • LinkedList：底层结构为链表，查询慢，增删慢
    • Vector：底层结构为数组，线程安全，效率低
  • set：接口，元素唯一性
    • HashSet：底层结构为Hash表。查询和增删效率都高
    • TreeSet：底层结构为红黑树，查询效率高于链表，增删效率高于数组，元素实现排序
    • LinkedHashSet：底层结构为hash表+链表，链表保证元素的有序

Map集合

双列集合，数据以键值对组成。 在map中值的可重复的，但键必须要是唯一的

HashMap

image.png

hashmap的底层原理：

  • 底层数据结构：哈希表 = 数组 + 链表 + 红黑树
  • 创建hashMap时，底层的数组容量是多少
  • 为什么用到红黑树？
  • 链表长度过长会降低查询效率，这时会转成红黑树，具体何时转换，何时再退化
    • 当链表数量为8时，转换为红黑树。
    • 当只有6个时退化为链表
  • 容量不足时底层数组进行扩容，具体多少扩容，新容量多少？
  • JDK7 与 JDK8中比较
  1. /* 增改 */
  2. V put(K key, V value);
  3. // 添加或修改散列表,添加时返回null,修改时返回原值
  4. void putAll(Map<? extends K, ?extends V> m);
  5. // 添加一个键值对类型相同的散列表
  6. boolean replace(K key, V value);
  7. // 修改后返回原值
  8. boolean replace(K key, V oldValue, V newValue); 
  9. // 只对key,oldValue修改newValue，修改成功返回true
  11. /* 删 */
  12. V remove(K key);
  13. // 删除某个键值对，并返回K对应的V
  14. void clear();
  15. // 清空散列表
  17. /* 查 */
  18. V get(K key);
  19. // K键查询V值， 
  20. V getOfDefault(k key, v valDefault);
  21. // k键查询v值，没有返回默认值
  22. Set<K> keySet();
  23. // 返回所有键
  24. Collection<V> values();
  25. // 返回所有值
  26. boolean isEmpty();
  27. // 判断散列表是否为空
  28. boolean containsKey(K key);
  29. // 判断键中是否有key
  30. boolean containsValue(V value);
  31. // 判断值中是否有value
  32. Set<Map.Entry<K,V>> entrySet();
  33. // 返回一个set的集合
  34. int size();
  35. // 返回散列表元素数量
  36. 封捷
  37. /* 进阶操作 */
  38. void replaceAll(BiFunction<?super k,?super v,?extends v> function); // (k,v) -> v+10
  39. // 对所有元素进行修改
  40. void forEach(BiFunction<?super k,?super v> action); // (k,v) -> System.out.println(k+v)
  41. // 映射指定操作，不会修改散列表
  42. V merge(K key, V value, BiFunction<?super v,?super v,?extends v>remappingFunction);
  43. // 判断k是否存在，如果不存在写入k v，否者oldValue和value在remappingFunction中计算
  44. V computeIfAbsent(k key, Function<?super k,?extends v>remappingFunction);
  45. // 检查是否有key，如果有不操作，如果没有remappingFunction并返回
  46. V computeIfPresent(k key, BiFunction<?super k,?super v,?extends v>remappingFunction); 
  47. // key, (k,v)->v+20
  48. // 检查是否有key，如果没有不操作，如果有remappingFunction并返回
  50. /* 遍历 */
  51. // keySet()获取所有键后，再遍历获取值
  52. for(K i: keySet()) 
  53.     System.out.println("key=" + i + "  value=" + get(i));
  55. // 获取一段键值对后使用getKey()和getValue()
  56. for(Map.Entry<String,Integer> item: entrySet())
  57.     System.out.println("key=" + item.getKey() + "  value=" + item.getValue());
  59. // 映射散列表
  60. forEach((k,v)-> System.out.println("key=" + k + "  value=" + v));
  62. // 获取所有值后使用增强for
  63. for(V v: values()) // 返回值
  64.     System.out.println("value=" + v);

sortedMap

TreeMap

基于红黑树(Red-Break tree) 的NavigableMap实现 该映射根据键的自然顺序进行排序，或则根据创建映射提供的Comparator进行排序

Hashtable

Properties

Set去重规则

保证添加的元素按照equals判断时，不能返回true。 true表示他们是相同的

  1. class Student{
  2.     String name; int age;
  3.     @Override
  4.     public boolean equals(Object o){
  5.         if(this==o) return true;
  6.         if(o==null ||| getClass()!=o.getClass())
  7.             return false;
  8.         Student s = (Student)o;
  9.         if(age!=s.age) return false;
  10.         return Objects.equals(name, s.name);
  11.     }
  12.     // 一致性：相同的对象，必须要有相同的散列码
  13.     // 在哈希表的链表中，
  14.     @Override
  15.     public int hashCode(){
  16.         return 31 * (name!=null?name.hashCode():0) + age;
  17.     }
  18.     @Override // java自带的散列码校准
  19.     public int hashCode() {
  20.         return Objects.hash(name, age);
  21.     }
  22.     // 31 -> (2<<5)-1, 哈希值越大冲突越小，尽量以2的n次幂-1为主
  23.     // 素数不能被1以外的数整除，也能减少冲突
  24. }

Tree排序规则

存储元素时根据当前加入与已有元素比较的结果决定元素加入的位置 Tree对象对比使用Comparator接口，重写Compare 结果负数时放左边，结果为正时放右边，结果为0时则覆盖

  3. /* 自定义排序规则1 */
  4. Map<Student, Integer> map = new TreeMap<>(new Comparator<Student>() {
  5.     @Override
  6.     public int compare(Student o1, Student o2) {
  7.         return o1.age - o2.age;
  8.     }
  9. });
  11. /* 自定义排序规则2 */
  12. Map<Student, Integer> map = new TreeMap<>(new Student());
  13. class Student implements Comparator<Student>{
  14.     String name;int age;
  15.     @Override
  16.     public int compare(Student o1, Student o2) {
  17.         return o1.age - o2.age;
  18.     }
  19. }