# 集合

# 常见的容器

• Collection
  • List：ArrayList，LinkedList，Vector等
  • Queue：BlockingQueue（接口）
  • Set：HashSet，LinkedHashSet，TreeSet
• Map：HashMap，LinkedHashMap，TreeMap，Properties，Hashtable，ConcurrentHashMap

# List 和 Set 异同（没代表性）

都继承自单列集合顶层接口Collection，都继承了Itrable接口用于遍历

• List：元素稳定（sort，遍历出的结果稳定，且存取顺序一致）、可重复

• Set：元素不可重复。

  元素不稳定（unsort，遍历出元素顺序由该元素HashCode决定，rehash后不一定一致），若是Linked~则是稳定的

# ArrayList & LinkedList & Vector 区别

• ArrayList：底层是数组，支持快速随机访问，增删慢（或涉及元素移动Arrays.copyOf System.arraycopy），线程不安全

  初始容量10，负载因子为1.0，扩容增量0.5

• LinkedList：底层是双向链表，查找慢，增删快，线程不安全；长度没有限制，占用空间比ArrayList大（维护指针）

• Vector：底层是数组，线程安全，性能差，即使为了线程安全也别用它

  初始容量10，负载因子为1.0，扩容增量1

  用Collections提供的静态方法**Collection.synchronizedCollection/List/Map/Set)**，甚至使用JUC中类

# 数组转集合 & 集合转数组

• 数组转集合。使用Arrays.asList(数组)转换的不是util包下的ArrayList，是Arrays类的内部类。不能修改长度！！！

  所以需要创建新集合，被转换的数组值也必须是对象！否则只是将数组整个转为集合（size为1）

  List<Object> objectList = ArrayList<Object> ( Arrays.asList (数组) )
  

• 集合转数组，需要指定一个数组

  String[] arr = new String[list.size()];//必须定义数组，否则下面代码返回的数组泛型丢失！还要指定容量，和集合一样即可
  list.toArray(arr);//若上面定义的数组容量够用，则直接保存到上面的数组中；否则这行代码有个返回值，即是转换后的数组
  

# HashSet 和 HashMap 区别

当链表长度超过阈值（8）时，将链表转换为红黑树，这样大大减少了查找时间

"重地"和""通话""元素不同，但哈希值相同，哈希冲突

# HashMap 的长度为什么是2的幂次方

哈希值范围是-2^31~2^31-1，这么长的数组内存放不下，所以一般先对数组长度求余数，余数即是要存放的数组下标。

取余操作中如果除数是2的幂次则等价于与其除数减一的与(&)操作（ hash%length==hash&(length-1)）

采用二进制&操作，相对取余提高运算效率，所以长度是2的幂次方。

# Hashtable & HashMap 区别

• Hashtable：线程安全，效率低，不允许null键和null值；继承自 Dictionary 类，都实现Map接口；有contains方法；

  初始容量

• HashMap：线程不安全，效率高，允许null键和null值；继承自AbstractMap 类，都实现Map接口；有containsKey/Value方法

  初始容量为16

# Hashtable 和 ConcurrentHashMap 区别

• 底层数据结构不同（Java 8 ）：
  • Hashtable：数组+链表
  • ConcurrentHashMap：数组+链表/红黑树
• 实现线程安全的方式不同：
  • Hashtable：使用 synchronized 来保证线程安全，即全表锁；多线程访问可能会阻塞，效率低下
  • ConcurrentHashMap：
    • 1.7 使用分段锁，对桶数组分段（Segment），每把锁只锁这一段数据，多线程访问不同段数据就不会阻塞
    • Java 8 使用 synchronized 和 CAS 来操作，只锁定当前链表或红黑二叉树的首节点，只要hash不冲突，就不会阻塞

# Hashcode 和 equals

• equals：默认调用的是 == ，一般根据需要重写。按照约定equals重写应该满足：自反性、对称性、传递性、一致性

• HashCode：返回对象的散列码，十进制整数。

  一般重写了equals必须重写HashCode。

  @Override
  public boolean equals(Object o) {
      if (this == o) return true;
      if (o == null || getClass() != o.getClass()) return false;
      Student student = (Student) o;
      return age == student.age &&
          Objects.equals(name, student.name);
  }
  

# 代码题

对HashMap<Integer,User>集合进行排序，按照User中age降序，排序时key，value不能拆散。

public static void main(String[] args) {
    HashMap<Integer, User> users = new HashMap<>();
    users.put(1, new User("zhangsan", 25));
    users.put(2, new User("lisi", 22));
    users.put(3, new User("wangwu", 28));
    System.out.println(users);

    HashMap<Integer, User> newUsers = sortMap(users);
    System.out.println(newUsers);
}

//要返回HashMap，所以不能用TreeMap
private static HashMap<Integer, User> sortMap(HashMap<Integer, User> map) {
    //不能拆散key，value，所以用Entry
    Set<Map.Entry<Integer, User>> entries = map.entrySet();
    //Colllections只能使用List来排序，所以需要将Set转List
    ArrayList<Map.Entry<Integer, User>> list = new ArrayList<>(entries);
    //排序，利用Lambda
    Collections.sort(list, (o1, o2) -> o2.getValue().getAge() - o1.getValue().getAge());

    //为防止元素由hash值排序不能用HashMap，所以采用LinkedHashMap，存取顺序不变
    LinkedHashMap<Integer, User> newMap = new LinkedHashMap<>();
    //遍历List并存入所以采用LinkedHashMap中
    list.forEach(o -> newMap.put(o.getKey(), o.getValue()));
    //LinkedHashMap是HashMap的子类，可以直接返回
    return newMap;
}