Java笔记(集合、散列表、Map、泛型)

一、集合

1.Set和排序

  • set：无序不可重复
  • 无序：不保证有序，就是有可能有序，有可能无序
  • 不可重复：不能添加重复数据
  • HashSet
  • TreeSet：底层是红黑树，会自动排序，意味着里面存储的必须是同类型的元素对象
  • 数字：从小到大排序
  • 字符串：一次比较每一位的ascll码值
  • 日期：自然日期顺序

1.1.TreeSet

public class Collection_01_TreeSet {
	public static void main(String[] args) {
		Set set=new TreeSet();
		//添加，不可重复
		set.add(1);
		set.add(2);
		set.add(6);
		set.add(5);
		set.add(2);
		System.out.println(set);
		//删除，只能根据内容删除
		set.remove(2);
		System.out.println(set);
		//遍历
		for (Object object : set) {
			System.out.println(object);
		}
		set=new TreeSet();
		set.add("1");
		set.add("6");
		set.add("18");
		set.add("10");
		//根据ascll码比较从第一位开始比较，后面每一位都进行比较
		System.out.println(set);
	}
}

  • 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

1.2.Comparable

  • 只有实现了comparable接口才可以自动排序，例如Integer，String
  • 如果我们添加的是自定义类型的对象，必须让该类也实现Comparable接口，并实现compareTo方法
  • 如果没有实现Comparable接口，向TreeSet中保存数据时会报错 类型转换异常( java.lang.ClassCastException: Day18.User cannot be cast to java.lang.Comparable )
@Override
	public int compareTo(Object o) {
		//this 是要添加的元素
		// 哦是集合中的元素
		if(o instanceof User){
			User oldUser=(User)o;
		//返回0说明相等，不再添加
		//返回大于0，说明要添加的元素比集合中的大，往后放
		//返回小于0，说明要添加的元素比集合中的小，往前放
			return this.age-oldUser.age;
		}
		return 0;
	}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13

源码

//把添加的对象转换为Comparable类型      
Comparable<? super K> k = (Comparable<? super K>) key;
            do {
                parent = t;
                //用要添加的元素调用compareTo方法把集合中的元素传入
                cmp = k.compareTo(t.key);
                if (cmp < 0) //返回值小于0的放左边
                    t = t.left;
                else if (cmp > 0)//返回值大于0的放右边
                    t = t.right;
                else
                    return t.setValue(value);//等于0则不添加
            } while (t != null);

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
import java.util.Set;
import java.util.TreeSet;

public class Collection_02_Sort {
	public static void main(String[] args) {
		//只有实现了comparable接口才可以自动排序，例如Integer，String
		//如果我们添加的是自定义类型的对象，必须让该类也实现Comparable接口，并实现compareTo方法
		//如果没有实现Comparable接口，向TreeSet中保存数据时会报错 类型转换异常( java.lang.ClassCastException: Day18.User cannot be cast to java.lang.Comparable )
		Set set=new TreeSet();
		set.add(new User(1));
		set.add(new User(66));
		set.add(new User(6));
		set.add(new User(666));
		System.out.println(set);
	}
}
class User implements Comparable{
	int age;
	public User(int age){
		this.age=age;
	}
	@Override
	public String toString() {
		return "User[age="+age+"]";
	}
	@Override
	public int compareTo(Object o) {
		//this 是要添加的元素
		// o 是集合中的元素
		if(o instanceof User){
			User oldUser=(User)o;
		//返回0说明相等，不再添加
		//返回大于0，说明要添加的元素比集合中的大，往后放
		//返回小于0，说明要添加的元素比集合中的小，往前放
			//return oldUser.age-this.age; 逆序
			return this.age-oldUser.age;
		}
		return 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
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40

1.3.Comparator

  • 场景1 :
  • 使用TreeSet保存的数字(Integer)类型,此时由于Integer实现了Comparable接口,并且是按数值大小进行升序排序
  • 假如 我们需要降序排序 怎么办?
  • 场景2 :
  • 使用TreeSet要保存的数据,并没有实现Comparable接口,这样是存不进去的,怎么解决?
  • 以上两种场景,可以使用 comparator接口解决 , 只要使用comparator之后, 不管原来是否有comparable 都会按照comparator来进行排序
  • comparator优先级较高

源码

//如果comparator不是空就调用compare方法，如果为空就先转换为comparable，再调用compareTo方法，所以comparator优先级要高于comparable
@SuppressWarnings("unchecked")
    final int compare(Object k1, Object k2) {
        return comparator==null ? ((Comparable<? super K>)k1).compareTo((K)k2)
            : comparator.compare((K)k1, (K)k2);
    }

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6

例：

import java.util.Comparator;
import java.util.Set;
import java.util.TreeSet;

public class Collection_03_Sort {
	public static void main(String[] args) {
		//将比较器类的对象传入就会按照比较器类的方式进行排序
		Set set =new TreeSet(new ComparatorImpl());
		set.add(1);
		set.add(666);
		set.add(6);
		set.add(66);
		System.out.println(set);
	}
}
//比较器类
class ComparatorImpl implements Comparator{
	@Override
	public int compare(Object o1, Object o2) {
        //o1是要添加的元素
		//o2是集合中的元素
		return (Integer)o2-(Integer)o1;
	}
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24

匿名内部类方式：

Set set=new TreeSet(new Comparator() {
	@Override
	public int compare(Object o1, Object o2) {
		return (Integer)o2-(Integer)o1;
	}
});
set.add(1);
set.add(666);
set.add(6);
set.add(66);
System.out.println(set);

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11

1.4.List排序

Collections中有一个sort方法，可以进行排序

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

public class Collection_04_Sort {
	public static void main(String[] args) {
		List list =new ArrayList();
		list.add(1);
		list.add(5);
		list.add(7);
		list.add(3);
		//之所以可以使用sort方法，是因为Integer实现了comparable接口
		Collections.sort(list);
		//如果添加的元素没有实现comparable接口，或者排序规则不是我们想要的，可以通过comparator实现
		Collections.sort(list, new Comparator() {
			@Override
			public int compare(Object o1, Object o2) {
				return (Integer)o2-(Integer)o1;
			}
		});
		System.out.println(list);
	}
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24

1.5.总结

Comparator 与 Comparable

  • 如果添加的元素类,是我们写的,比如 User ,那么我们想要排序,可以使用comparable来解决,这样还能保留comparator的扩展性

  • 如果添加的元素类,不是我们写的,意味着我们没办法修改对应的源码,就使用comparator来解决

2.Set

  • List 有序可重复
    • ArrayList : 查询快,底层是数组
    • LinkedList : 添加删除快,底层是双向链表
  • Set 无序不可重复
    • HashSet : 底层是散列表
    • TreeSet : 底层是红黑树,元素必须有序
  • Map 无序,key不能重复,value能重复,保存映射关系
    • HashMap : 底层是散列表
    • TreeMap : 底层是红黑树,元素必须有序

2.1.HashSet的使用

import java.util.HashSet;
import java.util.Set;

public class Collection_05_HashSet {
	public static void main(String[] args) {
		Set set=new HashSet();
		//不能重复
		set.add(1);
		set.add("c");
		set.add(7);
		set.add("b");
		set.add("c");
		set.add(6);
		set.add("a");
		//根据内容删除
		set.remove("c");
		for (Object object : set) {
			System.out.println(object);
		}
		System.out.println(set);
	}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21

二、散列表

1.概述

  • 散列表又叫哈希表，数组中保存的是单向链表

  • hash算法 : 是一种安全的加密算法,可以把不定长数据改为定长数据,并且不保证其唯一性

  • 其中算法包括 : 直接寻址法,数字分析法,平方取中法,折叠法,随机数法,除留余数法

  • map特性 : 无序,key不可重复,value可重复, 保存的是key和value键值对

  • Node : 1 key , 2 value , 3 next , 4 hash

  • 添加过程 :

    • 添加数据时(key,value) , 调用key的hashCode方法,生成hash值,然后通过hash算法得到数组下标
    • 如果该下标对应的空间中,没有数据,就创建一个Node对象,把key和value封装进去,保存到对应的下标上
    • ​ 如果该下标对应的空间中有数据,则调用key的equals方法,和空间中所有的数据进行比较
    • 如果没有相同的,则创建一个Node对象,保存在这个单向链表中的尾部
    • 如果equals判断有相同的,则不添加对应的key,value值替换原来的value

    1.8开始,为了提高查询效率,对链表进行了优化,如果数组对应的链表中的数据大于等于7(第八个),会把链表转换为红黑树

    当红黑树的个数小于6,则转换为链表

    红黑树：

    1. 节点是红色或黑色
    2. 根节点是黑色
    3. 每个叶子结点都是黑色的空节点（null）
    4. 不能有两个相邻的红色节点
    5. 从任一节点到每个叶子的所有路径都包含相同数目的黑色节点

源码：

static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;
        final K key;
        V value;
        Node<K,V> next;

        Node(int hash, K key, V value, Node<K,V> next) {
            this.hash = hash;
            this.key = key;
            this.value = value;
            this.next = next;
        }

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
 /**
     * The default initial capacity - MUST be a power of two.
     */
	//数组默认长度16
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

    /**
     * The maximum capacity, used if a higher value is implicitly specified
     * by either of the constructors with arguments.
     * MUST be a power of two <= 1<<30.
     */
	//最大容量2^30
    static final int MAXIMUM_CAPACITY = 1 << 30;

    /**
     * The load factor used when none specified in constructor.
     */
    //加载因子
    static final float DEFAULT_LOAD_FACTOR = 0.75f;

    /**
     * The bin count threshold for using a tree rather than list for a
     * bin.  Bins are converted to trees when adding an element to a
     * bin with at least this many nodes. The value must be greater
     * than 2 and should be at least 8 to mesh with assumptions in
     * tree removal about conversion back to plain bins upon
     * shrinkage.
     */
	//链表个数达到8个，就转型红黑树
    static final int TREEIFY_THRESHOLD = 8;

    /**
     * The bin count threshold for untreeifying a (split) bin during a
     * resize operation. Should be less than TREEIFY_THRESHOLD, and at
     * most 6 to mesh with shrinkage detection under removal.
     */
	//红黑树个数小于6就转换为链表
    static final int UNTREEIFY_THRESHOLD = 6;

    /**
     * The smallest table capacity for which bins may be treeified.
     * (Otherwise the table is resized if too many nodes in a bin.)
     * Should be at least 4 * TREEIFY_THRESHOLD to avoid conflicts
     * between resizing and treeification thresholds.
     */
    static final int MIN_TREEIFY_CAPACITY = 64;

  • 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

2.添加

public V put(K key, V value) {
        return putVal(hash(key), key, value, false, true);
    }

  • 1
  • 2
  • 3
static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

  • 1
  • 2
  • 3
  • 4
 final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        if ((tab = table) == null || (n = tab.length) == 0)
            //第一次添加时，创建散列表，长度默认16
            n = (tab = resize()).length;
     //就散下标，然后获取下标对应的数据
        if ((p = tab[i = (n - 1) & hash]) == null)
            //如果为null，说明改下表没有值
            tab[i] = newNode(hash, key, value, null);
        else {
            Node<K,V> e; K k;
            //p是数组中保存的第一个节点对象
            //判断key是否和p相同
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            else if (p instanceof TreeNode)
                //到这里说明key和p不一样，然后判断是否是红黑树类型
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            else {//到这里说明是链表
                for (int binCount = 0; ; ++binCount) {
                    if ((e = p.next) == null) {
                        p.next = newNode(hash, key, value, null);
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            //如果链表长度大于等于7转换红黑树
                            treeifyBin(tab, hash);
                        break;
                    }
                     if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;
                }
            }
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);//如果key已存在，则把value覆盖
                return oldValue;
            }
        }

  • 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

三、Map

1.继承体系

在这里插入图片描述

2.常用方法

在这里插入图片描述

3.HashMap

在使用hashSet 和 hashMap的时候,想要代表对象的唯一性,需要同时覆写hashCode方法和equals方法

public class Collection_06_Hash {
	public static void main(String[] args) {
		HashMap map=new HashMap();
		//key不能重复，重复不添加
		map.put("a", "a1");
		map.put("b", "b1");
		//根据key删除这个映射关系
		map.remove("a");
		//如果key是未有的key，则为添加，如果key已存在，则是修改
		//修改的是value值，key不能修改
		map.put("b","b2");
		//根据key获取value值
		System.out.println(map.get("b"));
		//个数
		map.size();
		//是否包含某个key
		map.containsKey("b");
		//是否包含某个value
		map.containsValue("b1");
		//是否为空(个数为0)
		map.isEmpty();
		//清空
		map.clear();
		System.out.println(map);
		//遍历相关 map不能直接遍历
		map.put("a", "a1");
		map.put("b", "b1");
		//获取所有value值
		map.values();
		//把map中所有的key保存到set中，并返回
		Set set=map.keySet();
		for (Object object : set) {
			System.out.println(object+":"+map.get(object));
		}
		//把key和value封装到entry中，然后保存在set中返回
		Set entrys=map.entrySet();
		for (Object object : entrys) {
			Entry entry=(Entry)object;
			System.out.println(entry.getKey()+":"+entry.getValue());
		}
	}
}

  • 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

4.TreeMap

public class Collection_07_TreeMap {
	public static void main(String[] args) {
		//和treeSet使用方式一样，只不过添加的时候需要使用put添加键值对
		TreeMap map=new TreeMap();
		//比较也是按照key比较，和value没有关系
		map.put("a", 666);
		map.put("a2", 666);
		map.put("a3", 666);
		map.put("a1", 666);
		//常用方法和HashMap类似
		System.out.println(map);
	}
}


  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14

四、泛型

1.概述

  • 泛型 : 编译时进行类型检查
  • 可以限制类型统一,并且在编译时进行类型校验,不符合条件的不能使用
  • 现在集合中 是可以保存任意元素 , 加上泛型之后,就只能保存某一种数据类型的元素
  • 泛型 不能写基本类型, 假如想写int ，就要写成Integer（int的包装类）

2.使用方式

public class Collection_08_Generic {
	public static void main(String[] args) {
		List list =new ArrayList();
		list.add(1);
		list.add("a");
		//未加泛型前可以传入各种类型
		for (Object object : list) {
			System.out.println(object);
		}
		List<String> list2=new ArrayList<String>();
		list2.add("a");
		//加了泛型后只可传入String类型（只能传一种）
		for (String string : list2) {
			System.out.println(string);
		}
	}
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17

3.注意

泛型 不能写基本类型, 假如想写int ，就要写成Integer（int的包装类）

4.自定义泛型

  • E : element的简写,一般代表元素,而集合中或者数组中的数据,我们叫元素
  • K V : 表示的是键值对,一般在map中存储
  • N : Number
  • T : type,表示具体的一个java类型
  • ? : 表示不确定的类型
  • 如果规定了泛型,但是不设置泛型的话,则默认为Object
public class Collection_09_Generic {
	public static void main(String[] args) {
		MyClass myClass=new MyClass();
		myClass.m1(1);
		myClass.m1("a");
		MyClass<String> myClass2=new MyClass<String>();
		//只可传入泛型所规定的数据类型
		myClass2.m1("a");
	}
}
class MyClass<T>{
	public void m1(T t){
		System.out.println(t);
	}
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15

5.面试题

  • Map以Value进行排序
  • Map是没有办法按照value排序的，因为源码中写死了，使用key进行比较
  • 所以只能保存到List中进行排序
public class Collection_10 {
	public static void main(String[] args) {
		Map<String,Integer> map=new HashMap<String, Integer>();
		map.put("a", 5);
		map.put("aaa", 9);
		map.put("aa", 7);
		map.put("6a6a6", 6);
		//把键值对取出
		Set set=map.entrySet();
		//转为list
		List<Entry<String, Integer>> list=new ArrayList<Map.Entry<String,Integer>>(set);
		//排序
		Collections.sort(list,new Comparator<Entry<String,Integer>>() {
			@Override
			public int compare(Entry<String, Integer> o1,
					Entry<String, Integer> o2) {
				//o1是要添加的元素，o2是集合中的元素
				//按value排序，大于零放后面，小于零放前面
				return o1.getValue()-o2.getValue();
			}
		});
		System.out.println(list);
	}
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
注：本文转载自blog.csdn.net的独行乡窝窝侠的文章"https://blog.csdn.net/m0_73783104/article/details/135707792"。版权归原作者所有，此博客不拥有其著作权，亦不承担相应法律责任。如有侵权，请联系我们删除。
复制链接
相关推荐
发表评论

评论记录：

未查询到任何数据！