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.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;
	}

源码

//把添加的对象转换为Comparable类型      
Comparable k = (Comparable) 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);

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.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)k1).compareTo((K)k2)
            : comparator.compare((K)k1, (K)k2);
    }

例：

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;
	}
}

匿名内部类方式：

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.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.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.概述

散列表又叫哈希表，数组中保存的是单向链表
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,则转换为链表

红黑树：

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

源码：

static class Node implements Map.Entry { final int hash;
        final K key;
        V value;
        Node next;
        Node(int hash, K key, V value, Node next) { this.hash = hash;
            this.key = key;
            this.value = value;
            this.next = next;
        }

 /**
     * 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;

2.添加

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

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

 final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) { Node[] tab; Node 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 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)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;
            }
        }

三、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());
		}
	}
}

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.概述

泛型 : 编译时进行类型检查
可以限制类型统一,并且在编译时进行类型校验,不符合条件的不能使用
现在集合中是可以保存任意元素 , 加上泛型之后,就只能保存某一种数据类型的元素

泛型不能写基本类型, 假如想写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 list2=new ArrayList();
		list2.add("a");
		//加了泛型后只可传入String类型（只能传一种）
		for (String string : list2) {System.out.println(string);
		}
	}
}

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 myClass2=new MyClass();
		//只可传入泛型所规定的数据类型
		myClass2.m1("a");
	}
}
class MyClass{public void m1(T t){System.out.println(t);
	}
}

5.面试题

Map以Value进行排序
Map是没有办法按照value排序的，因为源码中写死了，使用key进行比较

所以只能保存到List中进行排序

public class Collection_10 {public static void main(String[] args) {Map map=new HashMap();
		map.put("a", 5);
		map.put("aaa", 9);
		map.put("aa", 7);
		map.put("6a6a6", 6);
		//把键值对取出
		Set set=map.entrySet();
		//转为list
		List> list=new ArrayList>(set);
		//排序
		Collections.sort(list,new Comparator>() {@Override
			public int compare(Entry o1,
					Entry o2) {//o1是要添加的元素，o2是集合中的元素
				//按value排序，大于零放后面，小于零放前面
				return o1.getValue()-o2.getValue();
			}
		});
		System.out.println(list);
	}
}

分类:热门推荐日期:2024-03-02浏览:1评论:0

一、集合

1.Set和排序

1.1.TreeSet

1.2.Comparable

1.3.Comparator

1.4.List排序

1.5.总结

2.Set

2.1.HashSet的使用

二、散列表

1.概述

2.添加

三、Map

1.继承体系

2.常用方法

3.HashMap

4.TreeMap

四、泛型

1.概述

2.使用方式

3.注意

4.自定义泛型

5.面试题

元素 类型

相关推荐