集合三

一、红黑树

• 数据结构：是一种自平衡的二叉查找树。
• 红黑树是在二叉平衡树的基础上为每个元素节点添加了一个有颜色的标记，每一个节点可以是红或者黑。
• 红黑树在遵守原有规则的基础上还要按照自己提供的红黑规则进行排序

二、HashSet集合

特点：

• 底层数据结构是哈希表

• 无序：不能保证存储和取出的顺序完全一种

• 无索引：没有带索引的方法，所以不能使用普通for循环遍历

• 不可重复：由于是Set集合，所以元素唯一

1、HashSet的两种遍历方式：迭代器与增强for

2、哈希值：哈希码值

是JDK根据对象的地址和属性中，计算出来的int类型的整数。

//Object类中有一个方法可以获取对象的哈希值。
public int hashCode() //根据对象的地址值计算出来的哈希值

因为对象的哈希值时由对象的地址值计算出来的所以我们new出来的对象哈希值是不同的，但是在两个对象中赋值相同的数据时，它们的哈希值也是不同的，存入集合时就出现了相同的元素。

通常我们都会对hashCode方法进行重写并且和equals方法一起使用。

重写后的hashCode方法是根据对象的属性值依据底层的复杂算法计算出来的，相同率非常低，当哈希值相同时还会和重写后的equals方法作比较进一步降低相同率。

总结

二、哈希表

哈希表是一种常见的数据结构。HashSet，HashMap底层都是由哈希表实现数据存储的。

• JDK1.8之前，底层采用的是数组+链表实现。

• JDK1.8之后，底层进行了优化，由数组+链表+红黑树实现。

HashSet1.7版本原理总结

底层结构：哈希表（数组+链表）

数组的长度默认为16，加载因子为0.75

首先会先获取元素的哈希值，计算出在数组中应存入的索引，判断该索引处是否为null，如果为null，直接添加。如果不是null，则与链表中的所有元素，通过equals方法比较属性值，只要有一个相同，就不存，如果一样，才会存入集合。

HashSet1.8版本原理解析：

底层结构:哈希表（数组，链表，红黑树的结合体）

当挂在下面的元素过多时，那么不利于添加，也不利于查询，所以在JDK8以后。

当链表长度超过8的时候，自动转换为红黑树。

存储流程不变。

三、Map集合

Interface Map<K,V>    K：键的数据类型，V：值得数据类型

1、HashMap集合

和HashSet一样的操作，HashSet底层就是用到HashMap结果存储数据的。

2、TreeMap集合

和TreeSet一样的操作，TreeSet底层就是用到TreeMap结果存储数据的。

1. 单列集合：每次添加只能存一个元素。

2. 双列集合：每次添加一对数据。（两个元素）分为键和值，键只能唯一，值可以相同，每一对数据我们称之为键值对对象也叫entry对象。

   • Map集合的特点

     • ​ 键值对映射关系

     • 一个键对应一个值

     • 键不能重复，值可以重复

     • 元素存储无序

       Map集合的使用

       public class MapDemo01 {public static void main(String[] args) {//创建集合对象Map<String,String> map = new HashMap<String,String>();//V put(K key, V value) 将指定的值与该映射中的指定键相关联map.put("itheima001","林青霞");map.put("itheima002","张曼玉");map.put("itheima003","王祖贤");map.put("itheima003","柳岩");//输出集合对象System.out.println(map);}
       }
       

       Map集合的常用方法

       方法名	说明
       V put(K key , V value)	添加元素
       V remove(Object key)	根据键删除键值对元素
       void clear()	移除所有的键值对元素
       boolean containsKey(Object key)	判断集合是否包含指定的键
       boolean containValue(Object value)	判断集合是否包含指定的值
       boolean isEmpty()	判断集合是否为空
       int size()	集合长度，也就是键值对个数

       案例

       public class MapDemo02 {public static void main(String[] args) {//创建集合对象Map<String,String> map = new HashMap<String,String>();//V put(K key,V value)：添加元素map.put("张无忌","赵敏");map.put("郭靖","黄蓉");map.put("杨过","小龙女");//V remove(Object key)：根据键删除键值对元素
       //        System.out.println(map.remove("郭靖"));
       //        System.out.println(map.remove("郭襄"));//void clear()：移除所有的键值对元素
       //        map.clear();//boolean containsKey(Object key)：判断集合是否包含指定的键
       //        System.out.println(map.containsKey("郭靖"));
       //        System.out.println(map.containsKey("郭襄"));//boolean isEmpty()：判断集合是否为空
       //        System.out.println(map.isEmpty());//int size()：集合的长度，也就是集合中键值对的个数System.out.println(map.size());//输出集合对象System.out.println(map);}
       }
       

       Map集合的获取方法

       方法名	说明
       V get(Object key)	根据键获取值
       Set keySet	获取所有键的集合
       Collection values()	获取所有值的集合
       Set<Map.Enty<K,V>> entrySet()	获取所有键值对对象的集合
       E getKey()	根据键值对对象获取键
       E getValues()	根据键值对对象获取值

       public class MapDemo03 {public static void main(String[] args) {//创建集合对象Map<String, String> map = new HashMap<String, String>();//添加元素map.put("张无忌", "赵敏");map.put("郭靖", "黄蓉");map.put("杨过", "小龙女");//V get(Object key):根据键获取值
       //        System.out.println(map.get("张无忌"));
       //        System.out.println(map.get("张三丰"));//Set<K> keySet():获取所有键的集合
       //        Set<String> keySet = map.keySet();
       //        for(String key : keySet) {
       //            System.out.println(key);
       //        }//Collection<V> values():获取所有值的集合Collection<String> values = map.values();for(String value : values) {System.out.println(value);}}
       }
       

集合的遍历思路：

方法一：

   1. 我们可以获取到集合中所有键值对对象2. 然后用迭代器或者增强for循环遍历3. 通过键值对对象调用getKey和getValue方法获取键和值

方法二：

      1. 我们可以通过集合的keySet方法获取到所有的键2. 然后通过迭代器或增强for循环遍历3. 获取到每一个键，通过集合对象调用get方法根据键获取到值**案例：**```javapublic class HashMapTest {public static void main(String[] args) {HashMap<String, String> hashMap = new HashMap<>();hashMap.put("1","张三");hashMap.put("2","李四");hashMap.put("3","王五");hashMap.put("4","赵六");hashMap.put("5","田七");Set<String> keySet = hashMap.keySet();  //增强for遍历：根据每一个键获取值for (String s : keySet) {System.out.println(s);String s1 = hashMap.get(s);System.out.println(s1);}System.out.println("======");Iterator<String> t = keySet.iterator(); //迭代器遍历while (t.hasNext()){String next = t.next();System.out.println(next);String s = hashMap.get(next);System.out.println(s);}System.out.println("-------");Set<Map.Entry<String, String>> entries = hashMap.entrySet();    //增强for遍历：更加键值对对象获取键和值for (Map.Entry<String, String> entry : entries) {String key = entry.getKey();String value = entry.getValue();System.out.println(key);System.out.println(value);}System.out.println("-----------");Iterator<Map.Entry<String, String>> it = entries.iterator();    //迭代器遍历while (it.hasNext()){Map.Entry<String, String> next = it.next();String key = next.getKey();String value = next.getValue();System.out.println(key);System.out.println(value);}}}```

四、Collections集合工具类

作用：

​ 针对集合操作的工具类。

Collections类的常用方法

方法名	说明
public static void sort(List list)	将指定的列表按升序排序
public static void reverse(List<?> list)	反转指定列表中的元素顺序
public static void shuffle(List<?> list)	使用默认的随机源随机排列指定的列表

案例：

public class CollectionsDemo01 {public static void main(String[] args) {//创建集合对象List<Integer> list = new ArrayList<Integer>();//添加元素list.add(30);list.add(20);list.add(50);list.add(10);list.add(40);//public static <T extends Comparable<? super T>> void sort(List<T> list)：将指定的列表按升序排序
//        Collections.sort(list);//public static void reverse(List<?> list)：反转指定列表中元素的顺序
//        Collections.reverse(list);//public static void shuffle(List<?> list)：使用默认的随机源随机排列指定的列表Collections.shuffle(list);System.out.println(list);}
}