java 集合框架详解(持续更新)_集合排序
赞
踩
单列集合（List、Set）
双列集合（Map）
拓展
散列（Hashing）是什么
散列表（Hash Table）是什么
Hash函数是什么
Hash值是什么
HashCode是什么
学习思路
掌握顶层 : 掌握顶层接口抽象类中(所有子类都可以使用)共性的方法
使用底层 : 顶层不是接口就是抽象类，无法创建对象使用，需要使用底层的子类创建对象使用
例如：
Collection 接口：定义所有单列集合中共性的方法，方法集中没有带索引的方法
List接口：有序的集合，允许存储重复的元素且存储和取出元素顺序相同；其有索引，可以使用普通的for 循环遍历
Set接口： 无序的集合，不允许存储重复元素；其没有索引，不能使用普通的for循环遍历
单列集合
-
Vector
（与ArrayList相似，区别是Vector是重量级的组件，使用使消耗的资源比较多。）
在考虑并发的情况下用Vector（保证线程的安全）。
在不考虑并发的情况下用ArrayList（不能保证线程的安全）。
4.ArrayList 拷贝
Java的拷贝可以分为三种：浅拷贝(Shallow Copy)、深拷贝(Deep Copy)、延迟拷贝(Lazy Copy)。
在java中除了基本数据类型之外（int,long,short等），还存在引用数据类型，例如String以及对象实例。
对于基本数据类型，实际上是拷贝它的值，而对于引用数据类型，拷贝的就是它的引用，并没有创建一个新的对象，即没有分配新的内存空间。这样的拷贝就称作浅拷贝。
深拷贝就是在引用类型进行拷贝时，创建了新的对象，即分配了新的内存空间给拷贝对象。下面就来具体看看浅拷贝和深拷贝的区别
List浅拷贝
众所周知，list本质上是数组，而数组的是以地址的形式进行存储。
如上图将list A浅拷贝给list B，由于进行的是浅拷贝，所以直接将A的内容复制给了B，java中相同内容的数组指向同一地址，即进行浅拷贝后A与B指向同一地址。造成的后果就是，改变B的同时也会改变A，因为改变B就是改变B所指向地址的内容，由于A也指向同一地址，所以A与B一起改变。
常见的浅拷贝：
遍历循环复制、
使用List实现类的构造方法、
使用list.addAll()方法
使用System.arraycopy()方法
//遍历循环复制
public static void main(String[] args) throws Exception {
List<Person> destList = new ArrayList<Person>(srcList.size());
for(Person p : srcList){
destList.add(p);
}
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
//使用List实现类的构造方法
public static void main(String[] args) throws Exception {
List<Person> destList = new ArrayList<Person>(srcList);
}
- 1
- 2
- 3
- 4
- 5
//使用list.addAll()方法
public static void main(String[] args) throws Exception {
List<Person> destList = new ArrayList<Person>();
destList.addAll(srcList);
}
- 1
- 2
- 3
- 4
- 5
- 6
//使用System.arraycopy()方法
public static void main(String[] args) throws Exception {
Person[] srcPersons=srcList.toArray(new Person[0]);
Person[] destPersons=new Person[srcPersons.length];
System.arraycopy(srcPersons, 0, destPersons, 0, srcPersons.length);
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
//使用Stream的方式copy
public static void main(String[] args) throws Exception {
List<Person> destList = srcList.stream().collect(Collectors.toList());
}
- 1
- 2
- 3
- 4
- 5
浅拷贝示例
public static void main(String[] args) throws Exception { List<Person> srcList = new ArrayList<Person>(); srcList.add(new Person(23,"fenghao")); srcList.add(new Person(24,"ferao")); List<Person> destList = new ArrayList<Person>(srcList.size()); for(Person p : srcList){ destList.add(p); } System.out.println(destList); //[Person{age=23, name='fenghao'}, Person{age=24, name='ferao'}] srcList.get(0).setAge(100);//改变B System.out.println(destList); //[Person{age=100, name='fenghao'}, Person{age=24, name='ferao'}] }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
List深拷贝
如图，深拷贝就是将A复制给B的同时，给B创建新的地址，再将地址A的内容传递到地址B。ListA与ListB内容一致，但是由于所指向的地址不同，所以改变相互不受影响。
深拷贝示例
public class A implements Cloneable { public String name[]; public A(){ name=new String[2]; } public Object clone() { A o = null; try { o = (A) super.clone(); } catch (CloneNotSupportedException e) { e.printStackTrace(); } return o; } } // for(int i=0;i<n;i+=){ // copy.add((A)src.get(i).clone()); // }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
在浅复制的情况下，源数据被修改破坏之后，使用相同引用指向该数据的目标集合中的对应元素也就发生了相同的变化。因此，在需求要求必须深复制的情况下，要是使用上面提到的方法，请确保List中的T类对象是不易被外部修改和破坏的。
-
LinkedHashSet
LinkedHashSet是HashSet的一个子类，LinkedHashSet也根据HashCode的值来决定元素的存储位置，但同时它还用一个链表来维护元素的插入顺序，插入的时候即要计算hashCode又要维护链表，而遍历的时候只需要按链表来访问元素。查看LinkedHashSet的源码发现它是样的
Collection接口
-
定义
单列集合的根接口，内部定义了单列集合共性的方法；它的子接口有List接口、Set接口
-
共性方法
方法 含义 boolean add(E e) 把给定的对象添加到当前的集合中 boolean remove( E e) 把给定的对象在当前的集合中删除 void clear() 清空集合中所有的元素 boolean isEmpty() 判断当前集合是否为空 boolean contains(E e) 判断当前集合中是否包含给定的对象 int size () 返回集合中元素的个数 Object[] toArray() 把集合中的元素，存储到数组中
List接口
-
描述
有序列表，允许存放重复的元素，且存储元素和取出元素的顺序是一致的，集合方法包含了一些索引的方法。
-
共性方法
方法 含义 boolean add(E e) 在集合顺序位置,依次添加元素 void add(int index，E element) 在集合指定位置,添加指定的元素 E set(int index ,E element) 在集合指定位置,替换为指定元素,返回值的更新前的元素 E get(int index) 在集合指定位置,返回元素 E remove(int index) 在集合指定位置,移除元素,返回的是被移除的元素 boolean removeAll(Collection<?> c) 在集合所有位置,移除指定 collection 中包含的所有元素,发生改变则返回true void clear() 清空集合中所有的元素 boolean isEmpty() 判断当前集合是否为空 boolean contains(E e) 判断当前集合中是否包含给定的对象 int size () 返回集合中元素的个数 Object[] toArray() 把集合中的元素，存储到数组中 -
实现类
实现类 线程安全性 特点 ArrayList 不安全 （数组实现）查询快，增删慢，轻量级 LinkedList 不安全 （双向链表实现）增删快，查询慢 Vector 安全 （数组实现）重量级 (使用少)
ArrayList类
-
特点
底层是Object数组，所以ArrayList具有数组的查询速度快的优点以及增删速度慢的缺点。
-
扩充机制
当元素数量达到当前容量时，它会创建一个新的、更大的数组，并将旧数组中的元素复制到新数组中。
新容量是旧容量的1.5倍，但会确保不超过数组的最大长度。频繁的扩容可能会影响性能，因此最好在设计时预估并设置合适的初始容量。
-
线程安全性
ArrayList 不是线程安全的。如果多个线程同时修改一个 ArrayList，那么可能会导致数据不一致或其他并发问题。
如果需要在多线程环境中使用 ArrayList，可以考虑使用其线程安全的替代品：
• Vector（但通常不推荐使用 Vector，因为它在性能上通常不如 ArrayList，并且已经过时）
• Collections.synchronizedList 方法来包装 ArrayList。
• 并发集合CopyOnWriteArrayList 或 ConcurrentLinkedQueue 等。
LinkedList类
-
特点
底层是一种双向循环链表。在此链表上每一个数据节点都由三部分组成：前指针（指向前面的节点的位置），数据，后指针（指向后面的节点的位置）。最后一个节点的后指针指向第一个节点的前指针，形成一个循环。
它查询效率低但是增删效率高。 -
实现队列
队列(Queue)是限定所有的插入只能在表的一端进行，而所有的删除都在表的另一端进行的线性表。
• 表中允许插入的一端称为队尾(Rear)
• 允许删除的一端称为队头(Front) -
实现栈
栈(Stack)也是一种特殊的线性表，是一种后进先出(LIFO)的结构。
• 栈是限定仅在表尾进行插入和删除运算的线性表，表尾称为栈顶(top)，表头称为栈底(bottom)。
• 栈的物理存储可以用顺序存储结构，也可以用链式存储结构。
Set接口
-
描述
没有对Collection接口进行功能上的扩充，只是比Colleciton接口更加严格了。
• 不允许存储重复的元素
• 没有索引（无带索引的方法） -
实现类
实现类 线程安全性 特点 HashSet 不安全 equals返回true，hashCode返回相同的整数；哈希表；存储的数据是无序的 LinkedHashSet 不安全 维护着一个运行于所有条目的双重链接列表。存储的数据是有序的 TreeSet 不安全
HashSet类
-
描述
底层是包装了一个HashMap去实现，采用HashCode算法来存取集合中的元素，因此具有比较好的读取和查找性能。
它内部元素顺序混乱（HashSet按HashCode存储对象（元素）决定的，对象变化则可能导致HashCode变化），元素值可为NULL
HashSet的equals和HashCode：
前面说过，Set集合是不允许重复元素的，否则将会引发各种奇怪的问题。那么HashSet如何判断元素重复呢？
HashSet需要同时通过equals和HashCode来判断两个元素是否相等，具体规则是，如果两个元素通过equals为true，并且两个元素的hashCode相等，则这两个元素相等（即重复）。
所以如果要重写保存在HashSet中的对象的equals方法，也要重写hashCode方法，重写前后hashCode返回的结果相等（即保证保存在同一个位置）。所有参与计算 hashCode() 返回值的关键属性，都应该用于作为 equals() 比较的标准。
试想如果重写了equals方法但不重写hashCode方法，即相同equals结果的两个对象将会被HashSet当作两个元素保存起来，这与我们设计HashSet的初衷不符（元素不重复）。
另外如果两个元素哈希Code相等但equals结果不为true，HashSet会将这两个元素保存在同一个位置，并将超过一个的元素以链表方式保存，这将影响HashSet的效率。
TreeSet类
TreeSet实现了SortedSet接口，顾名思义这是一种排序的Set集合，查看jdk源码发现底层是用TreeMap实现的，本质上是一个红黑树原理。 正因为它是排序了的，所以相对HashSet来说，TreeSet提供了一些额外的按排序位置访问元素的方法，例如first(), last(), lower(), higher(), subSet(), headSet(), tailSet().
-
排序方式
• 自然排序
• 定制排序-
自然排序（在元素中写排序规则）
• 实现Comparable接口，调用compareTo方法比较元素大小
对于TreeSet判断元素是否重复的标准，也是调用元素从Comparable接口继承而来额compareTo方法，如果返回0则是重复元素（两个元素I相等）。Java的常见类都已经实现了Comparable接口，下面举例说明没有实现Comparable存入TreeSet时引发异常的情况。
-
定制排序（在集合中写排序规则）:TreeSet还有一种排序就是定制排序，定制排序时候，需要关联一个Comparator对象，由Comparator提供排序逻辑。
如果链表的长度超过8位，那么就会把链表转换为红黑树（提高查询速度）
Map接口
-
描述
Map接口是集合框架的第二类接口树。提供了一组键值的映射。其中键是唯一的。
-
内部方法
方法 作用 boolean isEmpty() 判断集合内是否存在元素 V put(K key , V value) 使用put方法添加键值对，如果map集合中没有该key对应的值，则直接添加，并返回null，如果已经存在对应的值，则会覆盖旧值，value为新的值 V putIfAbsent(K key, V value) 使用putIfAbsent方法添加键值对，如果map集合中没有该key对应的值，则直接添加，并返回null，如果已经存在对应的值，则依旧为原来的值 V get(Object key) 根据指定的值在集合中获取对应值，返回值：key存在，返回对应的vlaue值，key不存在返回Null V remove(Object key) 把指定的键所对应的键值对元素，在集合中删除，返回被删除元素的值 boolean containsKey(Object key) 判断集合中是否包含指定的值 V getOrDefault(Object key, V defaultValue) 集合中若没有该键，则返回默认值 Set KeySet() 获取集合中所有的键，存储到Set集合中 Set<Map.Entry<k,v>> entrySet() 获取到Map集合中所有的键值对对象的集合（Set集合） void forEach(BiConsumer<? super K, ? super V> action) JDK8强化了针对 Map 类的迭代方式，新增了一个默认方法 forEach，它接收一个 BiConsumer 函数。官方解释对此映射中的每个条目执行给定操作，直到所有条目已处理或操作引发异常。其中BiConsumer用于两个参数之间进行操作的函数式接口，是 BiConsumer这个函数式接口正好用来操作 Map 的 key 和 value -
实现类
实现类 线程安全性 特点 HashMap 不安全 键不重复，可null键或值 TreeMap 不安全 对key排好序的Map（key 的实现是TreeSet） LinkedHashMap 不安全 维护着一个运行于所有条目的双重链接列表。存储的数据是有序的 Hashtable 安全 不允许null的键或值 Properties 安全 Hashtable的子类，key和value都是String类型，用来读配置文件
HashMap类
-
描述
根据键的HashCode值存储数据,根据键可以直接获取它的值，具有很快的访问速度。
-
构造方法
方法 参数作用 HashMap() 默认构造函数 HashMap(int capacity) 指定“容量大小” HashMap(int capacity, float loadFactor) 指定“容量大小”和“加载因子” HashMap(Map<? extends K, ? extends V> map) 包含“子Map”的构造函数 -
键值对存储结构
通过哈希函数将key映射到数组的某个位置，并将value存储在这个位置。
数据量变大后，发生哈希冲突，即多个key映射到同一数组位置，此时使用链表来存储key-value对JDK8：数组+单向链表+红黑树(链表的长度超过8转换)
JDK7：数组+单向链表 -
扩容机制
当HashMap中的元素数量超过其容量阈值（容量 * 负载因子）时，会触发扩容操作。
• 初始容量 = 16
• 加载因子 = 0.75
• 阈值 = 初始容量 × 加载因子 = 16 × 0.75 =12扩容操作会创建一个新的数组，扩容策略是当前容量翻倍。
然后将原来数组中的元素重新计算哈希值后存储到新数组中。 -
线程安全性
它不是线程安全的，内部没有同步机制，意味着当多个线程同时修改HashMap时，它们可能会同时对数据操作，导致数据不一致或其他不可预见的行为。
-
存储示例
少量数据存储：
hashmap.put("apple","b");• index = Hash(
apple) ：根据键经由Hash算法计算Hash值，即数组下标位置
• 在数组对应下标位置放置"b"大量数据存储：
hashmap.put("apple","b"); ...• index = Hash(
apple) ：根据键经由Hash算法计算Hash值，即数组下标位置2
• index = Hash(orange) ：根据键经由Hash算法计算Hash值，即数组下标位置2
• 在数组对应位置，变化为链表的头节点，通过Next指针指向它的下一个Entry节点，重复数据依次插入链表即可
TreeMap类
-
TreeMap
TreeMap基于红黑树（Red-Black tree）实现。该映射根据其键的自然顺序进行排序（如:对Integer来说，其自然排序就是数字的升序；对String来说，其自然排序就是按照字母表排序），或者根据创建映射时提供的 Comparator 进行排序，具体取决于使用的构造方法。另外，TreeMap是非同步的。 它的iterator 方法返回的迭代器是fail-fastl的。
单列集合用例
ArrayList
-
排序
public static void main(String[] args) throws Exception { List<Integer> list =new ArrayList(); list.add(7); list.add(6); list.add(5); list.add(2); list.add(1); list.add(3); Collections.sort(list); for (int a : list){ System.out.print(a+"\t"); } }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
-
剔除特定元素
public static void main(String[] args) throws Exception { List<String> list = new ArrayList<String>(); list.add("A"); list.add("A"); list.add("C"); list.add("D"); Iterator<String> it = list.iterator(); while(it.hasNext()){ if(it.next().equals("A")){ it.remove(); } } System.out.println(list.toString()); }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
LinkedList
@Test
public void linkedTest(){
LinkedList<String> ll = new LinkedList<>();
ll.add("李梅");
ll.add("李四");
ll.add("丽丽");
ll.add("莉莉");
System.out.println(ll);
ll.addFirst("www");
System.out.println(ll);
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
HashSet
-
相同对象存放一次
@Test public void HashSetTest(){ HashSet<People> set = new HashSet<>(); People p1 = new People("小美女",18); People p2 = new People("小美女",18); People p3 = new People("小美女",10); System.out.println(p1.hashCode());//1878246837 System.out.println(p2.hashCode());//929338653 System.out.println(p1==p2);//false System.out.println(p1.equals(p2));//false set.add(p1); set.add(p2); set.add(p3); System.out.println(set); }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
现在对People实体重写HashCode和equals，结果变为
-
遍历
@Test public void HashSetTest(){ //迭代遍历 Set<String> set = new HashSet<String>(); Iterator<String> it = set.iterator(); while (it.hasNext()) { String str = it.next(); System.out.println(str); } //for循环遍历 for (String str : set) { System.out.println(str); } //优点还体现在泛型 假如 set中存放的是Object Set<Object> objectSet = new HashSet<Object>(); for (Object obj : objectSet) { if (obj instanceof Integer) { int aa = (Integer) obj; } else if (obj instanceof String) { String aa = (String) obj; } } }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
LinkedHashSet
@Test
public void LinkedHashSetTest(){
LinkedHashSet<String> ll = new LinkedHashSet<>();
ll.add("sss");
ll.add("www");
ll.add("qq");
ll.add("ss");
ll.add("ss");
ll.add("xx");
System.out.println(ll);
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
TreeSet
-
自然排序
@Test public void TreeSetTest(){ Set set = new TreeSet(); set.add(new Err()); set.add(new Err()); set.add(new Err()); System.out.println(set); } class Err implements Comparable{ @Override public int compareTo(Object o) { return 0; //当compareTo方法返回0的时候集合中只有一个元素 //return 1; //当compareTo方法返回正数的时候集合会怎么存就怎么取 //return -1; //当compareTo方法返回负数的时候集合会倒序存储 } }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
-
定制排序
@Test public void TreeSetTest(){ Set set = new TreeSet(new MyCommpare()); set.add(new M(5)); set.add(new M(3)); set.add(new M(9)); System.out.println(set); } class M { int age; public M(int age) { this.age = age; } } class MyCommpare implements Comparator { @Override public int compare(Object o1, Object o2) { M m1 = (M) o1; M m2 = (M) o2; return m1.age > m2.age ? 1 : m1.age < m2.age ? -1 : 0; } }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
双列集合用例
HashMap
-
getOrDefault()方法
Map<String, Integer> map = new HashMap<>(); map.put("a", null); map.put("b", 2); map.put("c", 3); System.out.println(map.getOrDefault("a", 100)); System.out.println(map.getOrDefault("d", 200));- 1
- 2
- 3
- 4
- 5
- 6
打印结果：null 200
-
putIfAbsent()方法
public static void main(String[] args) { // 创建一个 HashMap HashMap<Integer, String> sites = new HashMap<>(); // 往 HashMap 添加一些元素 sites.put(1, "Google"); sites.put(2, "Runoob"); sites.put(3, "Taobao"); System.out.println("sites HashMap: " + sites); // HashMap 不存在该key sites.putIfAbsent(4, "Weibo"); // HashMap 中存在 Key sites.putIfAbsent(2, "Wiki"); System.out.println("Updated Languages: " + sites); }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
打印结果：
sites HashMap: {1=Google, 2=Runoob, 3=Taobao}
Updated sites HashMap: {1=Google, 2=Runoob, 3=Taobao, 4=Weibo} -
存null键值
public static void main (String[] args) { HashMap<Object, Object> map = new HashMap<>(); map.put(null,"a"); map.put("b",null); map.put(null,null); System.out.println(map); }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
-
存自定义类型键值-string
public static void main(String[] args) { HashMap<String,Person> map = new HashMap<>(); //Map集合保证key是唯一的：作为key的元素，必须重写hashCode方法和equals方法，以保证key唯一 //String类型重写hashCode方法和equals方法，可以保证key唯一 map.put("1",new Person(1,"丽丽")); map.put("2",new Person(2,"莉莉")); map.put("3",new Person(3,"李丽")); map.put("1",new Person(4,"莉莉")); Set<String> set =map.keySet(); for (String o : set){ Person usr = map.get(o); System.out.println(o+":"+usr); } }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
-
存自定义类型键值-实体类
public static void main(String[] args) { HashMap<Person,String> map = new HashMap<>(); //必须重写hashCode方法和equals方法，以保证key唯一 map.put(new Person(1,"莉莉"),"1"); map.put(new Person(2,"丽丽"),"1"); map.put(new Person(3,"李丽"),"1"); map.put(new Person(1,"莉莉"),"1"); Set<Person> set = map.keySet(); for (Person o : set){ System.out.println(o.getAge()+":"+o.getName()+"--"+map.get(o)); } }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
-
键找值遍历
public static void main(String[] args) { Map<String,Integer> map = new HashMap<>(); map.put("李林",160); map.put("丽丽",161); map.put("莉莉",162); Set<String> set = map.keySet(); for (String o : set){ int a = map.get(o); System.out.println(o+" "+a); } }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
-
Entry遍历
public static void main(String[] args) { Map<String,Integer> map = new HashMap<>(); map.put("李林",160); map.put("丽丽",161); map.put("莉莉",162); Set<Map.Entry<String,Integer>> set = map.entrySet(); Iterator<Map.Entry<String,Integer>> it = set.iterator(); while(it.hasNext()){ Map.Entry<String,Integer> entry = it.next(); String key = entry.getKey(); Integer value = entry.getValue(); System.out.println(key+"="+value); } }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
-
lamda表达式遍历
public static void main(String[] args) { Map<String, Integer> map = new HashMap<>(); map.put("李林", 160); map.put("丽丽", 161); map.put("莉莉", 162); map.forEach((key, value) -> { System.out.println(key + "：" + value); }); }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
Hashtable
public static void main (String[] args)
{
Hashtable<Object, Object> table = new Hashtable<>();
table.put(null,"a");
table.put("b",null);
table.put("b",null);
System.out.println(table);
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
TreeMap
-
按照自然排序
public static void main (String[] args) { TreeMap<Integer, String> treeMap = new TreeMap<>(); treeMap.put(3, "val"); treeMap.put(2, "val"); treeMap.put(1, "val"); treeMap.put(5, "val"); treeMap.put(4, "val"); System.out.println(treeMap); }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
-
指定的comparator排序
public static void main (String[] args) { TreeMap<Integer, String> map = new TreeMap<>(Comparator.reverseOrder()); map.put(3, "val"); map.put(2, "val"); map.put(1, "val"); map.put(5, "val"); map.put(4, "val"); System.out.println(map); }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
-
给定的map创建一个TreeMap
public static void main (String[] args) { Map<Integer, String> map = new HashMap<>(); TreeMap<Integer, String> treeMap = new TreeMap<>(map); }- 1
- 2
- 3
- 4
- 5
Hashtable类
-
扩容机制
当Hashtable中的元素数量超过其容量阈值（容量 * 负载因子）时，会触发扩容操作。
• 初始容量 = 11
扩容操作会创建一个新的数组，扩容策略是容量翻倍+1
然后将原来数组中的元素重新计算哈希值后存储到新数组中。 -
线程安全性
它是线程安全的，所有方法都通过synchronized关键字进行了同步，以确保在并发访问时的数据一致性
ConcurrentHashMap类
-
使用原因
HashTable容器使用synchronized来保证线程安全，在线程竞争激烈的情况下HashTable的效率非常低下
-
定义
采用了Segment分段技术，容器里有多把锁，每把锁用于锁容器其中一部分数据，那么当多线程访问容器里不同数据段的数据时，线程间就不会存在锁竞争，从而可以有效的提高并发访问效率。
遍历及排序的工具
Comparable排序
java.lang.Comparable是一个排序接口， 此接口给实现类提供了一个排序的方法，此接口有且只有一个方法。
public int compareTo(T o);
compareTo方法接受任何类型的参数，来进行比较
list或者数组实现了这个接口能够自动的进行排序，当使用Collections/Arrays类的方法的sort()时，它会按照compareTo（）方法中定义的那样进行排序
SortedMap 接口的key内置了compareTo方法来进行键排序，SortedSet 也是内置了compareTo方法作为其内部元素的比较手段
compareTo()方法的返回值是int类型，相关含义如下：
int a = 10,b = 20,c = 30,d = 30;
a.compareTo(b) // 返回 -1 说明 a 要比 b 小
c.compareTo(b) // 返回 1 说明 c 要比 b 大
d.compareTo(c) // 返回 0 说明 d 和c 相等
- 1
- 2
- 3
- 4
真实环境使用的步骤如下：
• A类实现了Compareble接口，并且重写了compareTo（）方法
• 定义排序方式，若返回1，当前对象排在目标对象的前面（从小到大）
若返回-1，当前对象排在目标对象的后面（从大到小）
若返回0，两个对象相等
Comparator排序
Comparable & Comparator 相当于一个比较器，作用和Comparable类似，也是使用Collections.sort() 和 Arrays.sort()来进行排序，也可以对SortedMap 和 SortedSet 的数据结构进行精准的控制。
只是 Comparable 是在集合内部定义的方法实现的排序，Comparator 是在集合外部实现的排序，所以，如想实现排序，就需要在集合外定义Comparator接口的方法或在集合内实现 Comparable接口的方法。
Comparator比较器的方法：
int compare(T o1, T o2);
compare() 方法的用法和Comparable 的 compareTo() 用法基本一样，这个方法不允许进行null值比较，会抛出空指针异常
常用的写法相对来说比较复杂，使用Comparator.comparing可以简化代码，看起来逻辑更清晰（查看示例）。
Iterator迭代器
概述
java.util.Iterator,此迭代器是一个接口无法直接使用，需要使用Iterator接口的实现类；获取实现的方式比较特殊，是通过Collection接口中iterator()方法，这个方法返回的就是迭代器的实现类对象。
迭代：Collection 集合元素的通用获取方式中，在取元素之前先要判断集合中有没有元素，如果有元素，就把这个元素取出来，继续在判断，如果还有就再取出来；一直把集合中的所有元素全部取出，这种取出方式专业术语叫迭代。
方法
| 方法 | 含义 |
|---|---|
| boolean hasNext() | 如果仍有元素可以迭代，则返回true |
| E next() | 返回迭代的下一个元素 |
使用方式
a. 使用集合中的方法iterator()获取迭代器的实现类对象 ;
b. 使用Iterator接口中的方法hasNext跑判断换有没下一个元素
c. 使用Iterator接口中的方法next取出集合中的下一个元素
示例
public static void main(String[] args) {
Collection<String> coll = new ArrayList<>();
coll.add("黎明");
coll.add("李明");
Iterator<String> it = coll.iterator();
while (it.hasNext()) {
String e = it.next();
System.out.println(e);
}
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
Collections工具类
概述
java.utils.Collecitons，用于对集合进行操作
方法
| 方法 | 内容 |
|---|---|
boolean addAll(Collection<T> c,T… elements) | 在集合中添加一些元素 |
void shuffle(List<?> list) | 打乱顺序，打乱集合顺序 |
void sort(List<T> list) | 将集合中元素按照默认规则排序；使用前提是被排序的集合里边存储的元素必须实现Comparable，并且重写接口中的方法compareTo定义排序的规则 |
void sort(List<T> list,Comparator<? super T>) | 将集合中元素按照指定规则排序 |
void sort(List<T> list) 排序规则:
//自定义比较的规则，比较两个人的年龄（this,参数User）
return 0; //认为元素都是相同的
return o.getId() - this.getId(); //年龄降序
return this.getId() - o.getId(); //年龄升序
示例
public static void main(String[] args) {
List<String> ll = new ArrayList<>();
Collections.addAll(ll,"a","b","c","d","e");
System.out.println(ll); //[a, b, c, d, e]
Collections.shuffle(ll);
System.out.println(ll); //[d, a, e, b, c]
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
public static void main(String[] args) {
List<Integer> ll = new ArrayList<>();
Collections.addAll(ll, 1, 5, 3, 7, 2);
System.out.println(ll);
//默认是升序
Collections.sort(ll); //[1, 5, 3, 7, 2]
System.out.println(ll); //[1, 2, 3, 5, 7]
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
public static void main(String[] args) {
List<String> ll = new ArrayList<>();
Collections.addAll(ll,"v","c","a","c","b");
System.out.println(ll); //[v, c, a, c, b]
Collections.sort(ll);
System.out.println(ll); //[a, b, c, c, v]
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
public class Maze { @Data @AllArgsConstructor @NoArgsConstructor static class User implements Comparable<User> { private int id; private String username; //重写排序的规则 @Override public int compareTo(User o) { //return 0; //认为元素都是相同的 //自定义比较的规则，比较两个人的年龄（this,参数User） //return o.getId() - this.getId(); //年龄降序 return this.getId() - o.getId(); //年龄升序 } } public static void main(String[] args) { List<User> ll = new ArrayList<>(); ll.add(new User(12, "张三")); ll.add(new User(10, "张三")); ll.add(new User(19, "张三")); ll.add(new User(9, "张三")); System.out.println(ll); //[Maze.User(id=12, username=张三), Maze.User(id=10, username=张三), Maze.User(id=19, username=张三), Maze.User(id=9, username=张三)] Collections.sort(ll); System.out.println(ll); //[Maze.User(id=9, username=张三), Maze.User(id=10, username=张三), Maze.User(id=12, username=张三), Maze.User(id=19, username=张三)] } }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
遍历及排序工具用例
Comparable用例
public static void main(String[] args) { List<Node> list=new ArrayList<Node>(); list.add(new Node("节点1",9L)); list.add(new Node("节点2",10L)); list.add(new Node("节点3",7L)); list.add(new Node("节点4",1L)); list.add(new Node("节点5",5L)); Collections.sort(list); for (Node n : list) { System.out.println(n.name+"\t"+" count："+n.count); } } private static class Node implements Comparable<Node>{ String name; double count; public Node(String name,Long count) { this.count=count; this.name=name; } @Override public int compareTo(Node o) { return (int) (this.count-o.count);//从小到大 //return (int) (o.count-this.count);//从大到小 } }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
Comparator用例
-
传统写法：
public static void main(String[] args) { List<Person> people = Arrays.asList( new Person("Joe", 24), new Person("Pete", 18), new Person("Chris", 21) ); Collections.sort(people, new Comparator<Person>() { @Override public int compare(Person a, Person b) { // TODO Auto-generated method stub return a.age < b.age ? -1 : a.age == b.age ? 0 : 1; } }); System.out.println(people); //[{name=Pete, age=18}, {name=Chris, age=21}, {name=Joe, age=24}] } @Data class Person { String name; int age; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
[只需要记住]返回负数,第一个参数放前面;
-
comparing方式简化代码
public static void main(String[] args) { List<Model> models = new ArrayList<>(); Model model1 = new Model(); model1.setAge(300); model1.setName("a"); models.add(model1); Model model2 = new Model(); model2.setAge(500); model2.setName("c"); models.add(model2); Model model3 = new Model(); model3.setAge(100); model3.setName("b"); models.add(model3); System.out.println("-----排序前-----"); // 排序前 for (Model contract : models) { System.out.println(contract.getName() + " " + contract.getAge()); } System.out.println("-----排序后，根据age排序-----"); Collections.sort(models, Comparator.comparing(Model::getAge)); // 排序后 for (Model model : models) { System.out.println(model.getName() + " " + model.getAge()); } System.out.println("-----排序后，根据age排倒序-----"); Collections.sort(models, Comparator.comparing(Model::getAge).reversed()); // 排序后 for (Model model : models) { System.out.println(model.getName() + " " + model.getAge()); } System.out.println("-----排序后，根据name排序-----"); Collections.sort(models, Comparator.comparing(Model::getName)); // 排序后 for (Model model : models) { System.out.println(model.getName() + " " + model.getAge()); } } @Data static class Model { private String name; private int age; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
散列是什么
-
定义
散列是一种函数，将任意长度的数据映射为固定长度的数据，这个固定长度的数据就是哈希值。
-
作用
被用于数据映射和存储。将数据映射到一个固定大小的数组中，这个数组被称为散列表。
-
比喻理解
散列就像是给每本书贴上一个独特的标签。这个标签是通过一种特殊的方法（散列函数）计算出来的，它代表了这本书的“特征”。
当散列表中的元素存放太满，就必须进行再散列，将产生一个新的散列表，所有元素存放到新的散列表中，原先的散列表将被删除。在Java语言中，通过负载因子(load factor)来决定何时对散列表进行再散列。例如：如果负载因子0.75，当散列表中已经有75%位置已经放满，那么将进行再散列。
负载因子越高(越接近1.0)，内存的使用效率越高，元素的寻找时间越长。负载因子越低(越接近0.0)，元素的寻找时间越短，内存浪费越多。
散列表（Hash Table）是什么
-
定义
散列表也叫哈希表，是一种以键值对形式存储数据的数据结构。
它将key值通过哈希函数映射到一个固定大小的数组索引上，称为哈希值（Hash Value）
-
比喻理解
散列表就像是图书馆的书架，它根据书的标签（哈希值）来排列书籍。每个标签对应书架上的一个位置，这样你就能快速找到你想要的书了。
Hash函数
-
定义
将任意长度的数据映射为固定长度的数据，这个固定长度的数据就是哈希值。
-
作用
主要用于数据的加密和解密，可以使用密钥（称为“盐”）来加密数据，这种技术增加了数据的安全性。即使攻击者得到了哈希函数的输出数据，但如果没有密钥，他们就无法解密数据。
Hash值是什么
-
作用
用于数据的完整性和安全性验证
HashCode是什么
-
定义
哈希码（Hash code）。用于唯一标识对象的整数值，它是根据对象的内容生成的，可以将对象映射到一个固定大小的索引或地址。
-
作用
用于对象在哈希表等数据结构中的快速查找和定位
