为了面试而战--集合(下)
之前我们已经学习过了单列集合,现在我们来学习另一种集合,双列集合。顾名思义,集合中包含两列,一列为键,一列为值,也就是键值对。键和值一一对应,键不可重复,键+值称为键值对。
一.Map
双列集合最顶层的接口是Map,底层实现类是HashMap和TreeMap,其中HashMap还有子类为LinkedHashMap。Map中的api其他的都有,功能是其他所有的双列集合都可以继承使用。
put():添加方法,小细节就是如果你存入的键值对,键是不存在的,那么直接把键值对对象添加到Map集合中,方法返回值为null。如果键存在的话,会覆盖原有的值,并且返回原来的value。
public static void main(String[] args) { Map<String, String> m = new HashMap(); m.put("郭靖", "黄蓉"); m.put("韦小宝", "沐剑屏"); m.put("尹志平", "小龙女"); String value = m.put("韦小宝", "双儿"); System.out.println(value);//沐剑屏 }
remove():删除方法,返回值为被删的value
clear():清空
containsKey(key):是否包含key
containsValue(value):是否包含value
isEmpty():是否为空
List和Set可以遍历,那Map也可以遍历。Map的遍历方式有三种:
- 键找值
- 键值对
- Lambda表达式
1.键找值
就是通过get方法,获取key对应的value。想象有多对夫妻,我们把丈夫分成一组,给他变成单列集合,遍历单例集合,可以用iterator,通过get方法就可以获取对应的妻子。
public static void main(String[] args) { Map<String, String> map = new HashMap(); map.put("尹志平", "小龙女"); map.put("郭靖", "穆念慈"); map.put("欧阳克", "黄蓉"); Set<String> keys = map.keySet();//keySet()方法可以把key包装成set集合 Iterator var3 = keys.iterator(); while(var3.hasNext()) { String key = (String)var3.next(); String value = (String)map.get(key);//通过get获取key对应的值 System.out.println(key + " = " + value); } }
2.键值对
键值对也称为键值对对象,Entry。通过获取键值对对象,在用get方法获取键和值。
Map<String, String> map = new HashMap(); map.put("标枪选手", "马超"); map.put("人物挂件", "明世隐"); map.put("御龙骑士", "尹志平"); //获取所有的键值对对象,并且封装到一个Set集合中 Set<Map.Entry<String,String>> entries = map.entrySet();//这个集合有泛型,泛型是键值对对象 //遍历entries,去得到里面的每一个键值对对象 for(Map.Entry<String,String> entry:entries){//entry ---> "标枪选手" "马超" //利用entry调用get获取键和值 String key = entry.getKey(); String value = entry.getValue(); System.out.println(key + "=" + value); }
3.lambda表达式
public static void main(String[] args) { Map<String, String> map = new HashMap(); map.put("鲁迅", "这句话是我说的"); map.put("曹操", "不可能绝对不可能"); map.put("刘备", "接着奏乐接着舞"); map.put("柯镇恶", "看我眼色行事"); /* foreach底层:底层就是遍历键值对对象,第二种方法,得到key和value放进accept中 */ /* default void forEach(BiConsumer<? super K, ? super V> action) { Objects.requireNonNull(action); for (Map.Entry<K, V> entry : entrySet()) { K k; V v; try { k = entry.getKey(); v = entry.getValue(); } catch(IllegalStateException ise) { // this usually means the entry is no longer in the map. throw new ConcurrentModificationException(ise); } action.accept(k, v); } } */ map.forEach(new BiConsumer<String, String>() { public void accept(String key, String value) { System.out.println(key + "=" + value); } }); System.out.println("-----------------------------------"); map.forEach((key, value) -> { System.out.println(key + "=" + value); }); }
4.HashMap底层原理
HashMap是Map的一个实现类,直接用Map的方法,无序、无索引、不重复。HashMap和HashSet底层一样,基于哈希表。区别就是HashMap根据键来计算哈希值,只要键的哈希值,计算出在数组中的索引。如果存储的位置有元素,会调用equals()比较键的属性值,和HashSet不一样的是,如果键里的数据一样,那么它会覆盖原有的entry对象,,也就是value改变了,这是put方法隐含的覆盖。不一样的话还是会变成链表,长度超过8并且数组长度>=64,自动转成红黑树。
HashMap也是通过hashCode方法和equals方法保证键的唯一。如果键存的是自定义对象,需要重写hashCode和equals方法,如果值存的是自定义对象,就不用重写了。
5.LinkedHashMap
另一种Map,由键决定:有序、不重复、无索引。有序是保证存取顺序一致,和LinkedHashSet一致,在哈希表的基础上加了双向链表,就能存取有序了。
6.TreeMap
TreeMap跟TreeSet底层原理一样,都是红黑树结构,增删改查性能较好-,不重复、无索引、可排序(根据键排序)。默认由键从小到大排序,也可以根据自己规定的排序规则。
排序规则:
- 实现Comparable接口,重写ComparaTo方法 (存String、Integer不用重写,他们都继承了这个接口。Integer,Double默认升序排列,String按照字母在ASCII表中对应的数字升序排列)
- 创建集合时传递Comparator比较器对象,指定比较规则。
public int compareTo(Student o) { //this:表示当前要添加的元素 //o:表示已经在红黑树中存在的元素 int i = this.getAge() - o.getAge(); i = i == 0 ? this.getName().compareTo(o.getName()) : i; return i; }
//要降序排列,就不能按照默认了,要创建对象的时候创建Comparator对象 TreeMap<Integer, String> tm = new TreeMap(new Comparator<Integer>() { public int compare(Integer o1, Integer o2) { //o1:当前添加的元素 //o2:表示已经在红黑树中存在的元素 //降序排列,随便试试,不用背 return o2 - o1; } }); tm.put(5, "可恰可乐"); tm.put(4, "雷碧"); tm.put(3, "九个核桃"); tm.put(2, "康帅傅"); tm.put(1, "粤利粤"); System.out.println(tm);
如果需要要对结果进行排序,默认使TreeMap;如果不需要对结果排序,就用HashMap。
7.HashMap底层源码
在HashMap中,每一个元素都是一个Node对象,一个键值对也就是一个Entry对象
1.看源码之前需要了解的一些内容 Node<K,V>[] table 哈希表结构中数组的名字 DEFAULT_INITIAL_CAPACITY: 数组默认长度16 DEFAULT_LOAD_FACTOR: 默认加载因子0.75 HashMap里面每一个对象包含以下内容: 1.1 链表中的键值对对象 包含: int hash; //键的哈希值 final K key; //键 V value; //值 Node<K,V> next; //下一个节点的地址值 1.2 红黑树中的键值对对象 包含: int hash; //键的哈希值 final K key; //键 V value; //值 TreeNode<K,V> parent; //父节点的地址值 TreeNode<K,V> left; //左子节点的地址值 TreeNode<K,V> right; //右子节点的地址值 boolean red; //节点的颜色 2.添加元素 HashMap<String,Integer> hm = new HashMap<>();//刚创建Map的时候不会创建底层数组table,只会给加载因子赋值为0.75 hm.put("aaa" , 111); hm.put("bbb" , 222); hm.put("ccc" , 333); hm.put("ddd" , 444); hm.put("eee" , 555); 添加元素的时候至少考虑三种情况: 2.1数组位置为null 2.2数组位置不为null,键不重复,挂在下面形成链表或者红黑树 2.3数组位置不为null,键重复,元素覆盖 //参数一:键 //参数二:值 //返回值:被覆盖元素的值,如果没有覆盖,返回null 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); } //参数一:键的哈希值 //参数二:键 //参数三:值 //参数四:如果键重复了是否保留 // true,表示老元素的值保留,不会覆盖 // false,表示老元素的值不保留,会进行覆盖 final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) { //定义一个局部变量,用来记录哈希表中数组的地址值。 //成员变量已经有数组的地址值table了,为什么还要创建局部变量呢?因为成员变量放在了堆中,每次找的话还得去堆中找,效率低 Node<K,V>[] tab; //临时的第三方变量,用来记录键值对对象的地址值 Node<K,V> p; //表示当前数组的长度 int n; //表示索引 int i; //把哈希表中数组的地址值,赋值给局部变量tab //第一次赋值的是null tab = table; if (tab == null || (n = tab.length) == 0){ //1.如果当前是第一次添加数据,底层会创建一个默认长度为16,加载因子为0.75的数组 //2.如果不是第一次添加数据,会看数组中的元素是否达到了扩容的条件 //如果没有达到扩容条件,底层不会做任何操作 //如果达到了扩容条件,底层会把数组扩容为原先的两倍,并把数据全部转移到新的哈希表中 tab = resize();//resize()是一个复杂的方法,就是在创建table数组,一开始创建的就是长为16的数组 //表示把当前数组的长度赋值给n n = tab.length; } //拿着数组的长度跟键的哈希值进行计算,计算出当前键值对对象,在数组中应存入的位置 i = (n - 1) & hash;//index //获取数组中对应元素的数据 p = tab[i]; //第一次肯定null if (p == null){ //底层会创建一个键值对对象,直接放到数组当中 tab[i] = newNode(hash, key, value, null);//newNode底层就是创建了键值对对象 }else { Node<K,V> e; K k; //p.hash就是原来数组里的键值对的hash值 //等号的左边:数组中键值对的哈希值 //等号的右边:当前要添加键值对的哈希值 //如果键不一样,此时返回false //如果键一样,返回true boolean b1 = p.hash == hash; if (b1 && ((k = p.key) == key || (key != null && key.equals(k)))){ e = p; } else if (p instanceof TreeNode){ //判断数组中获取出来的键值对是不是红黑树中的节点 //如果是,则调用方法putTreeVal,把当前的节点按照红黑树的规则添加到树当中。 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); //判断当前链表长度是否超过8,如果超过8,就会调用方法treeifyBin //treeifyBin方法的底层还会继续判断 //判断数组的长度是否大于等于64 //如果同时满足这两个条件,就会把这个链表转成红黑树 if (binCount >= TREEIFY_THRESHOLD - 1) treeifyBin(tab, hash); break; } //e: 0x0044 ddd 444 //要添加的元素: 0x0055 ddd 555 //小概率会发生哈希碰撞,所以还要再比较一下。如果哈希值一样,就会调用equals方法比较内部的属性值是否相同 if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))){ break; } p = e; } } //如果e为null,表示当前不需要覆盖任何元素 //如果e不为null,表示当前的键是一样的,值会被覆盖 //e:0x0044 ddd 555 //要添加的元素: 0x0055 ddd 555 if (e != null) { V oldValue = e.value; if (!onlyIfAbsent || oldValue == null){ //等号的右边:当前要添加的值 //等号的左边:0x0044的值 e.value = value; } afterNodeAccess(e); return oldValue; } } //threshold:记录的就是数组的长度 * 0.75,哈希表的扩容时机 16 * 0.75 = 12 if (++size > threshold){ resize(); } //表示当前没有覆盖任何元素,返回null return null; }
8.TreeMap底层源码
1.TreeMap中每一个节点的内部属性 K key; //键 V value; //值 Entry<K,V> left; //左子节点 Entry<K,V> right; //右子节点 Entry<K,V> parent; //父节点 boolean color; //节点的颜色 2.TreeMap类中中要知道的一些成员变量 public class TreeMap<K,V>{ //比较器对象 private final Comparator<? super K> comparator; //根节点 private transient Entry<K,V> root; //集合的长度 private transient int size = 0; 3.空参构造 //空参构造就是没有传递比较器对象 public TreeMap() { comparator = null; } 4.带参构造 //带参构造就是传递了比较器对象。 public TreeMap(Comparator<? super K> comparator) { this.comparator = comparator; } 5.添加元素 public V put(K key, V value) { return put(key, value, true); } 参数一:键 参数二:值 参数三:当键重复的时候,是否需要覆盖值(和HashMap相反) true:覆盖 false:不覆盖 private V put(K key, V value, boolean replaceOld) { //获取根节点的地址值,赋值给局部变量t //和HashSet一样,成员变量有是有,但是放在了堆内存,查询效率低 Entry<K,V> t = root; //判断根节点是否为null //如果为null,表示当前是第一次添加,会把当前要添加的元素,当做根节点 //如果不为null,表示当前不是第一次添加,跳过这个判断继续执行下面的代码 if (t == null) { //方法的底层,会创建一个Entry对象,把他当做根节点 addEntryToEmptyMap(key, value);//添加键值对到空的Map中,底层就是创建一个Entry对象,地址存放在root中 //表示此时没有覆盖任何的元素 return null; } //不为null //表示两个元素的键比较之后的结果 int cmp; //表示当前要添加节点的父节点 Entry<K,V> parent; //表示当前的比较规则 //如果我们是采取默认的自然排序,那么此时comparator记录的是null,cpr记录的也是null //如果我们是采取比较器排序方式,那么此时comparator记录的是就是比较器 Comparator<? super K> cpr = comparator;//就是new的时候形参里是否有new了比较器对象 //表示判断当前是否有比较器对象 //如果传递了比较器对象,就执行if里面的代码,此时以比较器的规则为准 //如果没有传递比较器对象,就执行else里面的代码,此时以自然排序的规则为准 if (cpr != null) { do { //把根节点当做当前节点的父节点 parent = t; cmp = cpr.compare(key, t.key); if (cmp < 0) t = t.left; else if (cmp > 0) t = t.right; else { V oldValue = t.value; if (replaceOld || oldValue == null) { t.value = value; } return oldValue; } } while (t != null); } else { //你这个时候就是在没有比较器Comparator对象的情况下排序,如果还不实现Comparable接口的话,那还怎么排序,必报错。 //把键进行强转,强转成Comparable类型的 //要求:键必须要实现Comparable接口,如果没有实现这个接口 //此时在强转的时候,就会报错。 Comparable<? super K> k = (Comparable<? super K>) key; do { //把根节点当做当前节点的父节点 parent = t; //调用compareTo方法,比较根节点和当前要添加节点的大小关系。k是要添加的,t是已经存在的节点,从根节点开始往下找 cmp = k.compareTo(t.key); if (cmp < 0) //如果比较的结果为负数 //那么继续到根节点的左边去找 t = t.left; else if (cmp > 0) //如果比较的结果为正数 //那么继续到根节点的右边去找 t = t.right; else { //如果比较的结果为0,会覆盖 覆盖规则和HashMap是一样的 V oldValue = t.value; if (replaceOld || oldValue == null) { t.value = value; } return oldValue; } } while (t != null);//这里就是说你找到的位置没有元素了,就是null。是null就不会再循环了,就可以把它插进去了 } //就会把当前节点按照指定的规则进行添加 addEntry(key, value, parent, cmp < 0); return null; } //向红黑树里添加值 private void addEntry(K key, V value, Entry<K, V> parent, boolean addToLeft) { Entry<K,V> e = new Entry<>(key, value, parent);//键、值、父节点地址 if (addToLeft) parent.left = e;//添加到左边,把父节点的left记录为当前节点 else parent.right = e; //添加完毕之后,需要按照红黑树的规则进行调整 fixAfterInsertion(e); size++; modCount++; } private void fixAfterInsertion(Entry<K,V> x) { //因为红黑树的节点默认就是红色的 x.color = RED; //按照红黑规则进行调整 //parentOf:获取x的父节点 //parentOf(parentOf(x)):获取x的爷爷节点 //leftOf:获取左子节点 while (x != null && x != root && x.parent.color == RED) { //判断当前节点的父节点是爷爷节点的左子节点还是右子节点 //目的:为了获取当前节点的叔叔节点 if (parentOf(x) == leftOf(parentOf(parentOf(x)))) { //表示当前节点的父节点是爷爷节点的左子节点 //那么下面就可以用rightOf获取到当前节点的叔叔节点,y就是叔叔节点 Entry<K,V> y = rightOf(parentOf(parentOf(x))); if (colorOf(y) == RED) { //叔叔节点为红色的处理方案 //把父节点设置为黑色 setColor(parentOf(x), BLACK); //把叔叔节点设置为黑色 setColor(y, BLACK); //把爷爷节点设置为红色 setColor(parentOf(parentOf(x)), RED); //把爷爷节点设置为当前节点 x = parentOf(parentOf(x)); } else { //叔叔节点为黑色的处理方案 //表示判断当前节点是否为父节点的右子节点 if (x == rightOf(parentOf(x))) { //表示当前节点是父节点的右子节点 x = parentOf(x); //左旋 rotateLeft(x); } setColor(parentOf(x), BLACK); setColor(parentOf(parentOf(x)), RED); rotateRight(parentOf(parentOf(x))); } } else { //表示当前节点的父节点是爷爷节点的右子节点 //那么下面就可以用leftOf获取到当前节点的叔叔节点 Entry<K,V> y = leftOf(parentOf(parentOf(x))); if (colorOf(y) == RED) { setColor(parentOf(x), BLACK); setColor(y, BLACK); setColor(parentOf(parentOf(x)), RED); x = parentOf(parentOf(x)); } else { if (x == leftOf(parentOf(x))) { x = parentOf(x); rotateRight(x); } setColor(parentOf(x), BLACK); setColor(parentOf(parentOf(x)), RED); rotateLeft(parentOf(parentOf(x))); } } } //把根节点设置为黑色 root.color = BLACK; } 6.课堂思考问题: 6.1TreeMap添加元素的时候,键是否需要重写hashCode和equals方法? 此时是不需要重写的。 6.2HashMap是哈希表结构的,JDK8开始由数组,链表,红黑树组成的。 既然有红黑树,HashMap的键是否需要实现Compareable接口或者传递比较器对象呢? 不需要的。 因为在HashMap的底层,默认是利用哈希值的大小关系来创建红黑树的 6.3TreeMap和HashMap谁的效率更高? 如果是最坏情况,添加了8个元素,这8个元素形成了链表,此时TreeMap的效率要更高 但是这种情况出现的几率非常的少。 一般而言,还是HashMap的效率要更高。 6.4你觉得在Map集合中,java会提供一个如果键重复了,不会覆盖的put方法呢? 此时putIfAbsent本身不重要。 传递一个思想: 代码中的逻辑都有两面性,如果我们只知道了其中的A面,而且代码中还发现了有变量可以控制两面性的发生。 那么该逻辑一定会有B面。 习惯: boolean类型的变量控制,一般只有AB两面,因为boolean只有两个值 int类型的变量控制,一般至少有三面(正数、负数、0),因为int可以取多个值。 6.5三种双列集合,以后如何选择? HashMap LinkedHashMap TreeMap 默认:HashMap(效率最高) 如果要保证存取有序:LinkedHashMap 如果要进行排序:TreeMap
学完HashMap和TreeMap的狄岑之后,筋疲力尽了,下面就剩下一点小的知识点处理啦
先看这部分,叫可变参数。什么叫可变参数,字面意思,方法形参的个数是可以发生变化的,0,1,2,3......格式就是属性类型...名字。比如int...args
public static void main(String[] args) { int sum = getSum(1, 2, 3, 4, 5, 6, 7, 8, 9, 10); System.out.println(sum); } /* 可变参数底层就是数组,只不过是Java帮我们创建好了 小细节要注意:可变参数最多写一个,如果出了可变参数外,还有其他形参,可变参数要写在形参的最后。可变参数理解为大胖子,有多少吃多少,如果可变参数在前面的话,传入的参数都被可变参数吃了,后面的啥也得不到。 */ public static int getSum(int... args) { int sum = 0; int[] var2 = args; int var3 = args.length; for(int var4 = 0; var4 < var3; ++var4) { int i = var2[var4]; sum += i; } return sum; }
下一个内容是Collections,注意这是Collections而不是Collection哦。那这是什么东西呢,他是定义在java.util包下的工具类,用来操作集合的工具,他不是集合,而是工具类。
常用的API有addAll(Collection<T> c,T...elements),批量添加元素而且只能往单列集合中批量添加。还有shuffle(List<?> list),用来打乱List集合元素的顺序。还有很多其他方法。
public static void main(String[] args) { ArrayList<String> list = new ArrayList(); Collections.addAll(list, new String[]{"abc", "bcd", "qwer", "df", "asdf", "zxcv", "1234", "qwer"}); System.out.println(list); Collections.shuffle(list); System.out.println(list); }
好了,这是集合的最后一部分了,不可变集合。什么是不可变集合呢:就是不可以被改变的集合,长度不能变,内容不能修改。简单来说你不想让别人修改集合中的内容,就给他提供一个不可变集合。这个人只能对这个集合进行查询操作。如何创建不可变集合呢,在List、Set、Map接口中,都存在一个静态的of方法,可以获取一个不可变集合。
public static void main(String[] args) { /* 创建不可变的List集合 "张三", "李四", "王五", "赵六" */ //一旦创建完毕之后,是无法进行修改的,在下面的代码中,只能进行查询操作 List<String> list = List.of("张三", "李四", "王五", "赵六"); System.out.println(list.get(0)); System.out.println(list.get(1)); System.out.println(list.get(2)); System.out.println(list.get(3)); System.out.println("---------------------------"); for (String s : list) { System.out.println(s); } System.out.println("---------------------------"); Iterator<String> it = list.iterator(); while(it.hasNext()){ String s = it.next(); System.out.println(s); } System.out.println("---------------------------"); for (int i = 0; i < list.size(); i++) { String s = list.get(i); System.out.println(s); } System.out.println("---------------------------"); //list.remove("李四"); //list.add("aaa"); list.set(0,"aaa"); }
//Set参数要保证唯一性,不然会报错 Set<String> set = Set.of("张三", "李四", "王五", "赵六");
//和Set一样,不能重复,会报错 //Map中的of方法,参数数量有上限,最多能传入20个,也就是10个键值对,不是可变参数类型 Map<String, String> map = Map.of("张三", "南京", "张三", "北京", "王五", "上海", "赵六", "广州", "孙七", "深圳", "周八", "杭州", "吴九", "宁波", "郑十", "苏州", "刘一", "无锡", "陈二", "嘉兴");
如果你要添加的键值对对象超过了10个,就不能用of了,可以用ofEntries(),他的参数是可变数组。
HashMap<String, String> hm = new HashMap<>(); hm.put("张三", "南京"); hm.put("李四", "北京"); hm.put("王五", "上海"); hm.put("赵六", "北京"); hm.put("孙七", "深圳"); hm.put("周八", "杭州"); hm.put("吴九", "宁波"); hm.put("郑十", "苏州"); hm.put("刘一", "无锡"); hm.put("陈二", "嘉兴"); hm.put("aaa", "111"); //利用上面数据获取一个不可变集合 //获取到所有的键值对对象Entry Set<Map.Entry<String,String>> entries = hm.entrySet(); //把entries变成一个数组 Map.Entry[] arr = new Map.Entry[0]; //toArray方法在底层会比较集合的长度和数组的长度 //如果集合的长度>数组的长度,数据在数组中放不下,此时会根据实际情况,重新创建数组 //如果集合的长度 <= 数组的长度,数据在数组中放的下,此时不会创建新的数组,而是直接用。 Map.Entry[] arr2 = entries.toArray(arr); //最后调用ofEntries() Map map = Map.ofEntries(arr2); //上述太麻烦,我们整理一下思路,简化代码 //首先我们要根据hm得到键值对集合Entry,然后把集合变成数组,最后调用ofEntries()方法 Map.ofEntries(hm.entrySet().toArray(new Map.Entry[0])); //jdk10之后,有了一种直接生成不可变集合的方法 Map<String,String> map = Map.copyOf(hm);
这篇文章结束了,上下两篇总结了集合中的基础知识,所谓基础不牢地动山摇,希望我的文章能对大家学习起到一点点帮助。
#我的实习求职记录##软件开发薪资爆料##23届找工作求助阵地##如何判断面试是否凉了#我是一个转码的小白,平时会在牛客中做选择题,在做题中遇到不会的内容就会去找视频或者文章学习,以此不断积累知识。这个专栏主要是记录一些我通过做题所学到的基础知识,希望能对大家有帮助