做个网站得花多少钱,关键词优化方法有什么步骤,毕业设计做网站答辩会问什么,英雄联盟网页制作素材文章目录 3.Map3.1 Map继承结构3.2 Map接口的常用方法3.3 遍历Map3.4 HashMap集合3.4.1 HashMap集合key的特点3.4.2 HashMap集合的key存储自定义类型3.4.3 哈希表3.4.3.1 哈希表的介绍3.4.3.2 哈希表的存储原理 3.4.4 存放在HashMap和HashSet集合key部分的元素必须同时重写hash… 文章目录 3.Map3.1 Map继承结构3.2 Map接口的常用方法3.3 遍历Map3.4 HashMap集合3.4.1 HashMap集合key的特点3.4.2 HashMap集合的key存储自定义类型3.4.3 哈希表3.4.3.1 哈希表的介绍3.4.3.2 哈希表的存储原理 3.4.4 存放在HashMap和HashSet集合key部分的元素必须同时重写hashCodeequals方法若equals返回true时hashCode必须相同。3.4.5 HashMap中的key可以存null3.4.6 手写HashMap的put和get方法3.4.7 HashMap在Java8后的改进包含Java83.4.8 HashMap初始化容量永远都是2的次幂3.4.9 HashMap的初始化容量的设置 3.5 LinkedHashMap3.6 Hashtable3.7 Properties3.8 一些树的介绍3.8.1 二叉树3.8.2 排序二叉树3.8.3 平衡二叉树AVL3.8.4 红黑二叉树 3.9 TreeMap3.9.1 TreeMap集合的key为自定义类型 4.Set4.1 HashSet4.2 LinkedHashSet4.3 TreeSet4.4 关于HashSet的面试题 5.Collections工具类 接上一篇
JavaSE-12笔记【集合1】 3.Map
3.1 Map继承结构 Map集合以key和value的键值对形式存储。key和value存储的都是引用。Map集合中key起主导作用。value是附属在key上的。SequencedMap是Java21新增的。LinkedHashMap和TreeMap都是有序集合。key是有序的HashMapHashtableProperties都是无序集合。key是无序的Map集合的key都是不可重复的。key重复的话value会覆盖。HashSet集合底层是new了一个HashMap。往HashSet集合中存储元素实际上是将元素存储到HashMap集合的key部分。HashMap集合的key是无序不可重复的因此HashSet集合就是无序不可重复的。HashMap集合底层是哈希表/散列表数据结构因此HashSet底层也是哈希表/散列表。TreeSet集合底层是new了一个TreeMap。往TreeSet集合中存储元素实际上是将元素存储到TreeMap集合的key部分。TreeMap集合的key是不可重复但可排序的因此TreeSet集合就是不可重复但可排序的。TreeMap集合底层是红黑树因此TreeSet底层也是红黑树。它们的排序通过java.lang.Comparable和java.util.Comparator均可实现。LinkedHashSet集合底层是new了一个LinkedHashMap。LinkedHashMap集合只是为了保证元素的插入顺序效率比HashSet低底层采用的哈希表双向链表实现。根据源码可以看到向Set集合中add时底层会向Map中put。value只是一个固定不变的常量只是起到一个占位符的作用。主要是key。
3.2 Map接口的常用方法 V put(K key, V value); 添加键值对 void putAll(Map? extends K,? extends V m); 添加多个键值对 V get(Object key); 通过key获取value boolean containsKey(Object key); 是否包含某个key(底层会调用equals方法) boolean containsValue(Object value); 是否包含某个value底层会调用equals方法 V remove(Object key); 通过key删除key-value void clear(); 清空Map int size(); 键值对个数 boolean isEmpty(); 判断是否为空Map Collection values(); 获取所有的value Set keySet(); 获取所有的key SetMap.EntryK,V entrySet(); 获取所有键值对的Set视图。 static K,V MapK,V of(K k1, V v1, K k2, V v2, K k3, V v3); 静态方法使用现有的key-value构造Map 示例代码
package maptest;import java.util.Collection;
import java.util.HashMap;
import java.util.Map;public class MapTest01 {public static void main(String[] args) {//创建一个Map集合MapInteger, String maps new HashMap();//添加键值对maps.put(1,赵倩);maps.put(2,王雷);maps.put(3, 张芝);System.out.println(键值对个数 maps.size());//根据key获取valueSystem.out.println(maps.get(2));//key对应的value不存在时返回nullSystem.out.println(maps.get(4));//判断是否包含某个keySystem.out.println(maps.containsKey(3));//判断是否包含某个valueSystem.out.println(maps.containsValue(王雷));//通过key删除键值对maps.remove(3);System.out.println(键值对个数 maps.size());//添加多个键值对MapInteger,String newMap new HashMap();newMap.put(4,刘柳);newMap.putAll(maps);//获取所有的valueCollectionString values newMap.values();for (String value:values) {System.out.println(value);}System.out.println(当前是否为空map maps.isEmpty());//清空mapmaps.clear();System.out.println(当前是否为空map maps.isEmpty());}
}运行结果
3.3 遍历Map
方式一通过keySet()方法获取所有key之后再通过key获取对应value
package maptest;import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.Set;public class MapTest02 {public static void main(String[] args) {//创建一个Map集合MapInteger, String maps new HashMap();//添加键值对maps.put(1,赵倩);maps.put(2,王雷);maps.put(3, 张芝);maps.put(4, 刘柳);//方式一通过keySet()方法获取所有key之后再通过key获取对应valueSetInteger keys maps.keySet();IteratorInteger it keys.iterator();while (it.hasNext()){Integer key it.next();String value maps.get(key);System.out.println(key : value);}System.out.println();//使用for-eachSetInteger keys1 maps.keySet();for (Integer key: keys1) {System.out.println(key : maps.get(key));}}
}运行结果
方式二通过EntrySet()方法直接获取key和value这种方式效率较高推荐使用
package maptest;import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.Set;public class MapTest02 {public static void main(String[] args) {//创建一个Map集合MapInteger, String maps new HashMap();//添加键值对maps.put(1,赵倩);maps.put(2,王雷);maps.put(3, 张芝);maps.put(4, 刘柳);//方式二通过EntrySet()方法SetMap.EntryInteger, String entries maps.entrySet();IteratorMap.EntryInteger, String it entries.iterator();while (it.hasNext()){Map.EntryInteger, String entry it.next();Integer key entry.getKey();String value entry.getValue();System.out.println(key : value);}System.out.println();//for-eachSetMap.EntryInteger, String entries2 maps.entrySet();for (Map.EntryInteger, String entry: entries2) {System.out.println(entry.getKey() : entry.getValue());}}
}运行结果
3.4 HashMap集合
3.4.1 HashMap集合key的特点
key是无序不可重复的。 无序存进去的顺序与取出的顺序不一定相同 不可重复具有唯一性如果key重复的话value会覆盖。
示例代码
package maptest;import java.util.HashMap;
import java.util.Map;
import java.util.Set;public class HashMapTest01 {public static void main(String[] args) {MapInteger, String map new HashMapInteger, String();map.put(111111115,张三);map.put(111111112,李四);map.put(111111113,王五);map.put(111111114,赵六);map.put(111111114,赵六2); //存储重复的keyvalue会覆盖SetMap.EntryInteger, String entries map.entrySet();for (Map.EntryInteger, String entry:entries) { //取出的顺序不一定与存入的顺序相同Integer key entry.getKey();String value entry.getValue();System.out.println(key : value);}}
}运行结果
3.4.2 HashMap集合的key存储自定义类型
自定义User类型已覆写toString方法和equals方法
package maptest;import java.util.Objects;public class User {private String name;private int age;public User() {}public User(String name, int age) {this.name name;this.age age;}public String getName() {return name;}public void setName(String name) {this.name name;}public int getAge() {return age;}public void setAge(int age) {this.age age;}Overridepublic String toString() {return User{ name name \ , age age };}Overridepublic boolean equals(Object o) {if(o null){return false;}if(o this){return true;}if(o instanceof User){User user (User) o;return user.age this.age user.name.equals(this.name);}return false;}
}
创建相应的map并遍历
package maptest;import java.util.HashMap;
import java.util.Map;
import java.util.Set;public class HashMapTest02 {public static void main(String[] args) {//key中存储自定义类型UserMapUser, String map new HashMapUser, String();//创建User对象User user1 new User(张三, 18);User user2 new User(李四, 23);User user3 new User(王五, 25);User user4 new User(张三, 18);//向map中存入元素map.put(user1,1111);map.put(user2,2222);map.put(user3,3333);map.put(user4,4444);//遍历mapSetUser users map.keySet();for (User user:users) {String value map.get(user);System.out.println(user value);}}
}运行结果 在重写了equals()方法的情况下对于equals()为true的User作为key其value并没有被覆盖而是都存入了map这与HashMap的存储结构【哈希表】有关。
3.4.3 哈希表
3.4.3.1 哈希表的介绍
HashMap的底层为散列表又称哈希表的存储结构【数组单向链表】每一个节点存储有四个值key、hash(哈希值或者叫哈希码由key调用hashCode()方法获得)、value、next(下一个节点的地址) ①哈希表是一种查询和增删效率都很高的一种数据结构非常重要在很多场合使用并且面试也很常见。必须掌握。 ②哈希表的查询和增删效率都好因为哈希表是“数组 链表”的结合体同时结合了二者的优点。 ③数组和链表的结合不是绝对的。哈希表可能是数组 链表数组 红黑树 数组 链表 红黑树等。 3.4.3.2 哈希表的存储原理
①哈希函数
通过哈希函数即hashCode()可以将一个Java对象映射为一个数字这个数字就是哈希值。就像现实世界中每个人对象都会映射一个身份证号哈希值一样。也就是说hashCode()方法的返回值就是哈希值。一个好的哈希函数可以让散列分布均匀。 ②哈希值也叫做哈希码。是哈希函数执行的结果。 ③哈希碰撞也叫做哈希冲突。当两个对象“哈希值%数组长度”之后得到的下标相同时就发生了哈希冲突。如何解决哈希冲突将冲突的挂到同一个链表上或同一个红黑树上。 ④以上描述凡是“哈希”都可以换为“散列”。 哈希表的put()方法的底层执行步骤(如上图)
对应的key调用hashCode()方法得到哈希值即Node中的hash通过“哈希值%数组长度”得到该键值对的存入数组的索引值这里可能产生哈希碰撞把键值对存入对应索引的位置对应两种情况假设计算的索引值为9 情况一如果索引为9的位置没有存储元素则将键值对封装为Node对象然后存入到索引为9的位置中。 情况二如果索引为9的位置有存储元素(有首节点)那么就遍历整个单链表如果遍历出来节点的key和添加键值对的key相同则做覆盖操作如果单链表遍历出来节点的key和添加键值对的key都不同则把添加键值对封装为Node对象最后插入到单链表的末尾。
哈希表的get()方法的底层执行步骤
对应的key调用hashCode()方法得到哈希值即Node中的hash通过“哈希值%数组长度”得到该键值对的存入数组的索引值从对应数组索引值的位置的链表中逐一开始查找直到找到key.equals返回true的节点返回其value值。
3.4.4 存放在HashMap和HashSet集合key部分的元素必须同时重写hashCodeequals方法若equals返回true时hashCode必须相同。
再回去想想刚刚哪个例子在重写了equals()方法的情况下对于equals()为true的User作为key其value并没有被覆盖而是都存入了map原因是并没有调用equals()方法由于并没有重写hashCode()方法所以这里两个User的哈希值肯定不一样而刚好“哈希值%数组长度”得到的索引值也不一样导致没有产生哈希碰撞直接就存进去了。
package maptest;import java.util.HashMap;
import java.util.Map;
import java.util.Set;public class HashMapTest02 {public static void main(String[] args) {//key中存储自定义类型UserMapUser, String map new HashMapUser, String();//创建User对象User user1 new User(张三, 18);User user2 new User(李四, 23);User user3 new User(王五, 25);User user4 new User(张三, 18);//向map中存入元素map.put(user1,1111);map.put(user2,2222);map.put(user3,3333);map.put(user4,4444);System.out.println(user1的哈希值 user1.hashCode());System.out.println(user2的哈希值 user2.hashCode());//遍历mapSetUser users map.keySet();for (User user:users) {String value map.get(user);System.out.println(user value);}}
}运行结果
所以重要原理 ①存放在HashMap和HashSet 集合key部分的元素必须同时重写hashCodeequals方法。 ②equals返回true时hashCode的返回值必须相同。
为什么要同时重写hashCodeequals方法
若equals方法返回true则表明两个对象为同一个对象而HashMap(HashSet)中的key是不可重复的所以两个对象只能放其中一个如果此时hashCode方法不重写则以对象的内存地址为基础产生哈希值得到的哈希值一定不相同则可能不会产生哈希碰撞使得两个对象都成功存入如此则违背了“HashMap(HashSet)中的key是不可重复的”这一原则。
在IDEA中直接“AltInsert”重写hashCodeequals方法即可非常方便且高效不需要自己手动重写 User修改如下
package maptest;import java.util.Objects;public class User {private String name;private int age;public User() {}public User(String name, int age) {this.name name;this.age age;}public String getName() {return name;}public void setName(String name) {this.name name;}public int getAge() {return age;}public void setAge(int age) {this.age age;}Overridepublic String toString() {return User{ name name \ , age age };}Overridepublic boolean equals(Object o) {if (this o) return true;if (o null || getClass() ! o.getClass()) return false;User user (User) o;return age user.age Objects.equals(name, user.name);}Overridepublic int hashCode() {return Objects.hash(name, age);}
}新运行结果
3.4.5 HashMap中的key可以存null
HashMap中的key可以存null但也只能存一个key为null的key不重复如果添加的键值对key为null则程序默认将该键值对存储到table数组中索引为0的位置。
package maptest;import java.util.HashMap;
import java.util.Map;
import java.util.Set;public class HashMapTest03 {public static void main(String[] args) {//key中存储自定义类型UserMapUser, String map new HashMapUser, String();//存入key为null的节点map.put(null, 11111);map.put(null, 22222);map.put(null, 33333);SetMap.EntryUser, String entries map.entrySet();for (Map.EntryUser, String entry:entries) {User key entry.getKey();String value entry.getValue();System.out.println(key : value);}}
}运行结果
3.4.6 手写HashMap的put和get方法
package maptest;/*** 手写HashMap的put和get方法*/
public class MyHashMapK,V {/*** 哈希表*/private NodeK,V[] table;/*** 集合中的键值对个数*/private int size;public MyHashMap() {//注意这里new数组的时候不能使用泛型new NodeK,V[16]这样写是错误的this.table new Node[16];}static class NodeK,V{/*** key*/K key;/*** 哈希值*/int hash;/*** value*/V value;/*** 下一个节点的内存地址*/NodeK,V next;/*** 构造一个节点对象* param key 键* param hash 哈希值* param value 值* param next 下一个节点的内存地址*/public Node(K key, int hash, V value, NodeK, V next) {this.key key;this.hash hash;this.value value;this.next next;}Overridepublic String toString() {return { key key , value value }\n;}}/*** 获取集合中键值对个数* return 个数*/public int size(){return size;}/*** 向MyHashMap中添加一个键值对* param key 键* param value 值* return value,如果key重复返回的是oldValue否则返回newValue*/public V put(K key, V value){/*【第一步】处理key为null的情况如果添加键值对的key就是null则将该键值对存储到table数组索引为0的位置。【第二步】获得key对象的哈希值如果添加键值对的key不是null则就调用key的hashcode()方法获得key的哈希值。【第三步】获得键值对的存储位置因为获得的哈希值在数组合法索引范围之外因此我们就需要将获得的哈希值转化为[0数组长度-1]范围的整数那么可以通过取模法来实现也就是通过“哈希值 % 数组长度”来获得索引位置i。【第四步】将键值对添加到table数组中当table[i]返回结果为null时则键键值对封装为Node对象并存入到table[i]的位置。当table[i]返回结果不为null时则意味着table[i]存储的是单链表。我们首先遍历单链表如果遍历出来节点的key和添加键值对的key相同那么就执行覆盖操作如果遍历出来节点的key和添加键值对的key都不同则就将键键值对封装为Node对象并插入到单链表末尾。*///第一步处理key为null的情况if(key null){return putForKeyNull(key,value);}//第二步获得key对象的哈希值int hash key.hashCode();//第三步获得键值对的存储位置int index Math.abs(hash % table.length);//第四步将键值对添加到table数组中NodeK,V node table[index]; //取出下标index位置的nodeif(node null){//下标为index的位置上为空table[index] new Node(key, hash, value, null);size;return value;}//下标为index的位置上有单向链表NodeK,V prev null;while (node ! null){//找到key等于当前传入key的节点if(node.key.equals(key)){V oldValue node.value;node.value value;return oldValue;}prev node;node node.next;}//没有找到key等于当前传入key的节点(插入尾插法)prev.next new Node(key,hash,value,null);size;return value;}/*** 处理添加key为null的键值对* param key* param value* return*/private V putForKeyNull(K key, V value) {NodeK,V node table[0];if(node null){//下标为0的位置上为空table[0] new Node(key,0,value,null);size;return value;}//下标为0的位置上有单向链表NodeK,V prev null;while (node ! null){if(node.key null){//找到key为null的节点V oldValue node.value;node.value value;return oldValue;}prev node;node node.next;}//没有找到key为null的节点(插入尾插法)prev.next new Node(key,0,value,null);size;return value;}/*** 根据key获取对应value* param key 键* return 值*/public V get(K key){/*【第一步】处理key为null的情况如果查询的key就是null则就在table数组索引为0的位置去查询。【第二步】获得key对象的哈希值如果查询的key不是null则就调用key的hashcode()方法获得key的哈希值。【第三步】获得键值对的存储位置因为获得的哈希值在数组合法索引范围之外因此我们就需要将获得的哈希值转化为[0数组长度-1]范围的整数那么可以通过取模法来实现也就是通过“哈希值 % 数组长度”来获得索引位置i。【第四步】遍历单链表根据key获得value值如果table[i]返回的结果为null则证明单链表不存在那么返回null即可如果table[i]返回的结果不为null时则证明单链表存在那么就遍历整个单链表。如果遍历出来节点的key和查询的key相同那么就返回遍历出来节点的value值如果整个单链表遍历完毕则遍历出来节点的key和查询的key都不相等那么就证明查询key在链表中不存在则直接返回null即可。*///第一步处理key为null的情况if(key null){NodeK,V node table[0];//索引为0的位置没有存储任何元素if(node null){return null;}//索引为0的位置存储了元素有单向链表while (node! null){if(node.key null){return node.value;}node node.next;}}//key不是null//第二步获得key对象的哈希值int hash key.hashCode();//第三步获得键值对的存储位置int index Math.abs(hash % table.length);//第四步遍历单链表根据key获得value值NodeK,V node table[index];if(node null){//下标为index的位置上为空return null;}//下标为index的位置上有单向链表while (node ! null){if(node.key.equals(key)){return node.value;}node node.next;}return null;}/*** 重写toString方法输出所有节点*/Overridepublic String toString() {StringBuilder stb new StringBuilder();for (int i 0; i table.length; i) {NodeK,V node table[i];if(node ! null){//如果node不为空遍历整个单向链表while (node ! null){stb.append(node);node node.next;}}}return stb.toString();}
}测试程序User与上面最终的User一致
package maptest;public class HashMapTest04 {public static void main(String[] args) {MyHashMapInteger,String map new MyHashMap();map.put(1111, 张三);map.put(2222, 李四);map.put(3333, 王五);map.put(4444, 赵六);map.put(1111, 张三2);map.put(null, 钱七);map.put(null, 钱七2);map.put(null, 钱七3);System.out.println(map);System.out.println(map.get(1111));//key为自定义类型UserMyHashMapUser,String userMap new MyHashMap();User user1 new User(张三, 18);User user2 new User(李四, 23);User user3 new User(王五, 25);User user4 new User(张三, 18);userMap.put(user1, 111);userMap.put(user2, 222);userMap.put(user3, 333);userMap.put(user4, 444);userMap.put(user1, aaa);System.out.println(userMap);System.out.println(userMap.get(user1));}
}运行结果
3.4.7 HashMap在Java8后的改进包含Java8
①初始化时机
Java8之前构造方法执行时初始化table数组。Java8之后第一次调用put方法时初始化table数组。 ②插入法Java8之前头插法Java8之后尾插法 ③数据结构Java8之前数组 单向链表Java8之后数组 单向链表 红黑树。最开始使用单向链表解决哈希冲突。如果结点数量 8并且table的长度 64。单向链表转换为红黑树。当删除红黑树上的结点时结点数量 6 时。红黑树转换为单向链表。 -
3.4.8 HashMap初始化容量永远都是2的次幂 ①HashMap集合初始化容量16第一次调用put方法时初始化 ②HashMap集合的容量永远都是2的次幂假如给定初始化容量为31它底层也会变成32的容量。 ③将容量设置为2的次幂作用是1加快哈希计算2减少哈希冲突。
为什么会加快哈希计算 首先使用二进制运算是最快的。当一个数字是2的次幂时例如数组的长度是2的次幂时hash (length-1) 的结果和 hash % length的结果相同。 注意 只有length是2的次幂时以上等式才会成立。因为使用 运算符让效率提升因此建议容量一直是2的次幂。为什么会减少哈希冲突 计算索引的底层运算是hash length - 1。 如果length是偶数length-1后一定是奇数奇数二进制位最后一位一定是1,1和其他二进制位进行与运算结果可能是1也可能是0这样可以减少哈希冲突让散列分布更加均匀。 如果length是奇数length-1后一定是偶数偶数二进制位最后一位一定是00和任何数进行与运算结果一定是0则只能利用数组中偶数位的索引位置进行存储这样就会导致发生大量的哈希冲突白白浪费了一半的空间。
3.4.9 HashMap的初始化容量的设置
当哈希表中的元素越来越多的时候散列碰撞的几率也就越来越高因为数组的长度是固定的从而导致单链表过长降低了哈希表的性能此时我们就需要对哈希表进行扩容操作。那么HashMap什么时候进行扩容呢当执行put()操作的时候如果HashMap中存储元素的个数超过数组长度*loadFactor的结果loadFactor指的是负载因子loadFactor的默认值一般为0.75那么就需要执行数组扩容操作。所谓的扩容操作就是把数组的空间大小扩大一倍然后遍历哈希表中元素把这些元素重新均匀分散到扩容后的哈希表中。例如默认情况下数组大小为16那么当HashMap中元素个数超过160.7512的时候就需要执行扩容操作把数组的大小扩展为21632然后重新计算每个元素在数组中的位置这是一个非常消耗性能的操作。为了避免扩容带来的性能损坏建议使用哈希表之前先预测哈希表需要存储元素的个数提前为哈希表中的数组设置合适的存储空间大小避免去执行扩容的操作进一步提升哈希表的性能。例如我们需要存储1000个元素按照哈希表的容量设置为2的整数次幂的思想我们设置哈希表的容量为1024更合适。但是0.75*1024 1024需要执行消耗性能的扩容操作因此我们设置哈希表的容量为2048更加合适这样既考虑了的问题也避免了扩容的问题。思考当我们创建一个HashMap对象设置哈希表的容量为15请问HashMap对象创建成功后哈希表的实际容量为多少呢实际容量为12因为即使设置哈希表的容量为15底层也会变为16而由于HashMap中存储元素的个数超过数组长度*loadFactor就会扩容所以在扩容前的实际能存储的容量为16*0.7512。
3.5 LinkedHashMap
LinkedHashMap集合和HashMap集合的用法完全相同不过LinkedHashMap可以保证插入顺序。LinkedHashMap集合因为可以保证插入顺序因此效率比HashMap低一些。LinkedHashMap是如何保证插入顺序的底层采用了双向链表来记录顺序。LinkedHashMap集合底层采用的数据结构是哈希表 双向链表。LinkedHashMap集合的key是有序不可重复。key部分也需要同时重写hashCode equals。key的取值可以为nullkey如果相同value也是覆盖。
存储结构图
示例代码
package maptest;import java.util.LinkedHashMap;
import java.util.Map;
import java.util.Set;public class LinkedHashMapTest01 {public static void main(String[] args) {MapInteger, String map new LinkedHashMap();map.put(100, 张三);map.put(5, 李四);map.put(3000, 王五);map.put(20, 赵六);map.put(100, 张三2);map.put(null,null);SetMap.EntryInteger, String entries map.entrySet();for (Map.EntryInteger, String entry:entries) {System.out.println(entry.getKey() : entry.getValue());}}
}运行结果有序插入顺序与取出顺序一致
3.6 Hashtable
Hashtable和HashMap一样底层也是哈希表。Hashtable的key和value都不能为null。Hashtable是线程安全的方法上都有synchronized关键字。使用较少因为保证线程安全有其他方式。Hashtable的初始化容量11。默认加载因子0.75Hashtable的扩容策略2倍。HashMap中能用的方法在Hashtable中也能用不过Hashtable中有一些传统方法这些方法不属于集合框架需要用Hashtable类型的对象调用 ①Enumeration keys(); 获取所有key的迭代器 ②Enumeration elements(); 获取所有value的迭代器迭代器Enumeration的相关方法 ①boolean hasMoreElements(); 是否含有元素 ②E nextElement(); 获取元素Hashtable和HashMap集合的区别 ①HashMap集合线程不安全效率高key和value允许null。 ②Hashtable集合线程安全效率低key和value不允许null。
示例代码
package maptest;import java.util.Enumeration;
import java.util.Hashtable;
import java.util.Map;
import java.util.Set;public class HashtableTest01 {public static void main(String[] args) {MapInteger,String map new Hashtable();map.put(100, 张三);map.put(5, 李四);map.put(3000, 王五);map.put(20, 赵六);map.put(100, 张三2);//java.lang.NullPointerException//map.put(123,null);//java.lang.NullPointerException//map.put(null,钱七);//java.lang.NullPointerException//map.put(null,null);//继承的迭代方法SetMap.EntryInteger, String entries map.entrySet();for (Map.EntryInteger, String entry:entries) {System.out.println(entry.getKey() : entry.getValue());}System.out.println();HashtableInteger,String hashtable (HashtableInteger, String) map;//Hashtable独有的迭代方式EnumerationInteger keys hashtable.keys(); //获取所有keywhile (keys.hasMoreElements()){Integer key keys.nextElement();System.out.println(key);}EnumerationString values hashtable.elements(); //获取所有valuewhile (values.hasMoreElements()){String value values.nextElement();System.out.println(value);}}
}运行结果
3.7 Properties
Properties被称为属性类。通常和xxx.properties属性文件一起使用。Properties的父类是Hashtable。因此Properties也是线程安全的。Properties不支持泛型key和value只能是String类型且均不能为null。Properties相关方法 ①Object setProperty(String key, String value); 和put方法一样。 ②String getProperty(String key); 通过key获取value ③SetString propertyNames(); 获取所有的key
示例代码
package maptest;import java.util.Enumeration;
import java.util.Properties;public class PropertiesTest01 {public static void main(String[] args) {//创建Properties对象Properties properties new Properties();//向对象中存储key和valueproperties.setProperty(jdbc.driver, com.mysql.jdbc.Driver);properties.setProperty(jdbc.user, root);properties.setProperty(jdbc.password,123456);properties.setProperty(jdbc.url, jdbc:mysql://localhost:3306/sunny);//通过key获取valueString driver properties.getProperty(jdbc.driver);String user properties.getProperty(jdbc.user);String password properties.getProperty(jdbc.password);String url properties.getProperty(jdbc.url);System.out.println(driver);System.out.println(user);System.out.println(password);System.out.println(url);System.out.println();//获取所有的keyEnumeration? names properties.propertyNames();while (names.hasMoreElements()){String name (String) names.nextElement();System.out.println(name properties.getProperty(name));}}
}运行结果
3.8 一些树的介绍
3.8.1 二叉树
叉树(BinaryTree)由一个结点及两棵互不相交的、分别称作这个根的左子树和右子树的二叉树组成。下图中展现了五种不同基本形态的二叉树。 (a) 为空树。 (b) 为仅有一个结点的二叉树。 © 是仅有左子树而右子树为空的二叉树。 (d) 是仅有右子树而左子树为空的二叉树。 (e) 是左、右子树均非空的二叉树。
3.8.2 排序二叉树
排序二叉树采用左小右大原则存储按照中序遍历方式自动就是排好序的。
中序遍历左根右前序遍历根左右后序遍历左右根
比如我们要将数据【14, 12, 23, 4, 16, 13, 8, 3】存储到排序二叉树中结果如下图所示
排序二叉树的问题 排序二叉树本身实现了排序功能可以快速检索。但如果插入的节点集本身就是有序的要么是由小到大排列要么是由大到小排列那么最后得到的排序二叉树将变成普通的链表其检索效率就会很差。
同上数据先进行排序变成【3, 4, 8, 12, 13, 14, 16, 23】然后存储到排序二叉树中显然就变成了链表如下图所示
3.8.3 平衡二叉树AVL
为了避免出现上述一边倒的存储提出了“平衡二叉树”。
在平衡二叉树中任何结点的两个子树的高度最大差别为1所以它也被称为高度平衡树。 增加和删除结点可能需要通过一次或多次树旋转来重新平衡这个树。结点的平衡因子是它的左子树的高度减去它的右子树的高度(有时相反)。带有平衡因子1、0或 -1的节点被认为是平衡的。带有平衡因子-2或2的节点被认为是不平衡的并需要重新平衡这个树。比如我们存储排好序的数据【3, 4, 8, 12, 13, 14, 16, 23】增加结点如果出现不平衡则通过节点的左旋或右旋重新平衡树结构最终平衡二叉树如下图所示另参见https://www.cs.usfca.edu/~galles/visualization/Algorithms.html
3.8.4 红黑二叉树
红黑二叉树(简称红黑树)它首先是一棵二叉树同时也是一棵自平衡的排序二叉树。 红黑树在原有的排序二叉树增加了如下几个要求
每个结点要么红色要么黑色。根结点永远是黑色。所有的叶子结点都是空结点(即null)并且是黑色的。每个红色结点的两个子结点都是黑色 (从每个叶子结点到根结点的路径上不会有两个连续的红色结点) 。从任一结点到其子树中每个叶子结点的路径都包含相同数量的黑色结点。每次新结点在插入时颜色是红色的。插入后会根据红黑树的约束条件进行树的旋转和颜色的调整。
自平衡的含义以上这些约束强化了红黑树的关键性质从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。这样就让树大致上是平衡的。
红黑树是一个更高效的检索二叉树JDK 提供的集合类 TreeMap、TreeSet 本身就是一个红黑树的实现。红黑树的基本操作插入、删除、左旋、右旋、着色。每插入或者删除一个节点可能会导致树不在符合红黑树的特征需要进行修复进行 “左旋、右旋、着色” 操作使树继续保持红黑树的特性。
3.9 TreeMap
①TreeMap底层就是红黑树。 ②TreeMap和HashMap用法一样只不过需要key排序的时候就可以使用TreeMap。 ③TreeMap的key可排序不可重复且不能是null不过value可以为null。 ④TreeMap的key也需要重写hashCode和equals方法。
key为内置类型时可排序示例代码
package maptest;import java.util.Map;
import java.util.Set;
import java.util.TreeMap;public class TreeMapTest01 {public static void main(String[] args) {//创建HashMap集合MapInteger, String map new TreeMap();//存入map.put(100, 张三);map.put(5, 李四);map.put(13, 王五);map.put(20, 赵六);map.put(100, 张三2);//java.lang.NullPointerException
// map.put(null, zhangzhang);map.put(1, 钱七);//遍历SetMap.EntryInteger, String entries map.entrySet();for (Map.EntryInteger, String entry: entries) {System.out.println(entry.getKey() entry.getValue());}}
}运行结果由于Integer实现了Comparable接口实现了compareTo方法是可排序的所以这里按key部分排序输出了
3.9.1 TreeMap集合的key为自定义类型
当TreeMap集合的key为自定义类型要使TreeMap集合的key可排序有两种方式
第一种方式key实现Comparable接口并且提供compareTo方法在该方法中添加了比较规则。(比较规则不变的话建议这种。)第二种方式创建TreeMap集合时传一个比较器比较器实现Comparator接口在compare方法中添加比较规则。
自定义类型User当前为不可排序
package maptest;import java.util.Objects;public class User {private String name;private int age;public User() {}public User(String name, int age) {this.name name;this.age age;}public String getName() {return name;}public void setName(String name) {this.name name;}public int getAge() {return age;}public void setAge(int age) {this.age age;}Overridepublic String toString() {return User{ name name \ , age age };}Overridepublic boolean equals(Object o) {if (this o) return true;if (o null || getClass() ! o.getClass()) return false;User user (User) o;return age user.age Objects.equals(name, user.name);}Overridepublic int hashCode() {return Objects.hash(name, age);}
}测试代码
package maptest;import java.util.Map;
import java.util.TreeMap;public class TreeMapTest02 {public static void main(String[] args) {//key中存储自定义类型UserMapUser, String map new TreeMap();//创建User对象User user1 new User(ccc, 18);User user2 new User(ddd, 33);User user3 new User(bbb, 15);User user4 new User(aaa, 18);//向map中存入元素map.put(user1,1111);map.put(user2,2222);map.put(user3,3333);map.put(user4,4444);System.out.println(map);}
}
运行结果由于TreeMap在根据key排序时试图将User转换为Comparable接口但这里没有实现这个接口导致出现类型转换异常
第一种方式示例代码
User实现Comparable接口
package maptest;import java.util.Objects;public class User implements ComparableUser{private String name;private int age;public User() {}public User(String name, int age) {this.name name;this.age age;}public String getName() {return name;}public void setName(String name) {this.name name;}public int getAge() {return age;}public void setAge(int age) {this.age age;}Overridepublic String toString() {return User{ name name \ , age age };}Overridepublic boolean equals(Object o) {if (this o) return true;if (o null || getClass() ! o.getClass()) return false;User user (User) o;return age user.age Objects.equals(name, user.name);}Overridepublic int hashCode() {return Objects.hash(name, age);}Overridepublic int compareTo(User o) {//年龄一致的话比较名字if(this.age o.age){return this.name.compareTo(o.name);}return this.age - o.age; //年龄不一致直接按年龄比较}
}测试代码如上不变运行结果
第二种方式示例代码 User还是原来的User不实现Comparable接口
package maptest;import java.util.Objects;public class User {private String name;private int age;public User() {}public User(String name, int age) {this.name name;this.age age;}public String getName() {return name;}public void setName(String name) {this.name name;}public int getAge() {return age;}public void setAge(int age) {this.age age;}Overridepublic String toString() {return User{ name name \ , age age };}Overridepublic boolean equals(Object o) {if (this o) return true;if (o null || getClass() ! o.getClass()) return false;User user (User) o;return age user.age Objects.equals(name, user.name);}Overridepublic int hashCode() {return Objects.hash(name, age);}
}再定义一个比较器这里使用匿名内部类
package maptest;import java.util.Comparator;
import java.util.Map;
import java.util.TreeMap;public class TreeMapTest03 {public static void main(String[] args) {//创建TreeMap时给构造方法传递一个比较器这里直接使用匿名内部类的方式传入比较器MapUser, String map new TreeMap(new ComparatorUser() {Overridepublic int compare(User o1, User o2) {return o1.getAge() - o2.getAge(); //按年龄比较}});//创建User对象User user1 new User(zhangsan, 18);User user2 new User(lisi, 23);User user3 new User(wangwu, 25);User user4 new User(zhaoliu, 16);//向map中存入元素map.put(user1,1);map.put(user2,2);map.put(user3,3);map.put(user4,4);System.out.println(map);}
}运行结果
4.Set
Set也是Collection集合家族的只不过Set底层都是Map所以上面先把Map学习了。
Set接口继承Collection没有任何新增任何方法。Set接口常用实现类包括HashSet、LinkedHashSet、TreeSet。
4.1 HashSet
HashSet底层就是HashMap往HashSet集合中存储元素实际上是放到了HashMap集合的key部分。因此放在HashSet集合中的元素要同时重写hashCodeequals。HashSet底层当然也是哈希表。HashSet集合存储元素特点无序不可重复。无序指的是存进去的顺序和取出的顺序不一定一样。
1示例代码无序不可重复
package settest;import java.util.HashSet;
import java.util.Set;public class HashSetTest01 {public static void main(String[] args) {SetInteger set new HashSet();//无序不可重复set.add(200);set.add(200);set.add(200);set.add(10);set.add(2);set.add(3000);System.out.println(set);SetString set2 new HashSet();//无序不可重复set2.add(aaa);set2.add(aaa);set2.add(bbb);set2.add(ccc);set2.add(ddd);set2.add(eee);System.out.println(set2);}
}运行结果
2示例代码自定义类型需要重写hashCode和equals方法
自定义Vip类未重写hashCode和equals方法
package settest;public class Vip {private int id;private int age;private String name;public Vip() {}public Vip(int id, int age, String name) {this.id id;this.age age;this.name name;}public int getId() {return id;}public void setId(int id) {this.id id;}public int getAge() {return age;}public void setAge(int age) {this.age age;}public String getName() {return name;}public void setName(String name) {this.name name;}Overridepublic String toString() {return Vip{ id id , age age , name name \ };}
}测试代码
package settest;import java.util.HashSet;
import java.util.Set;public class HashSetTest02 {public static void main(String[] args) {//创建HashSetSetVip vips new HashSet();//创建Vip对象Vip vip1 new Vip(111,20,zhangsan);Vip vip2 new Vip(111,20,zhangsan);Vip vip3 new Vip(111,20,zhangsan);//存入vips.add(vip1);vips.add(vip2);vips.add(vip3);System.out.println(vips);}
}运行结果三个key内容相同的都存进去了 自定义Vip类增加重写hashCode和equals方法
package settest;import java.util.Objects;public class Vip {private int id;private int age;private String name;public Vip() {}public Vip(int id, int age, String name) {this.id id;this.age age;this.name name;}public int getId() {return id;}public void setId(int id) {this.id id;}public int getAge() {return age;}public void setAge(int age) {this.age age;}public String getName() {return name;}public void setName(String name) {this.name name;}Overridepublic String toString() {return Vip{ id id , age age , name name \ };}Overridepublic boolean equals(Object o) { if (this o) return true;if (o null || getClass() ! o.getClass()) return false;Vip vip (Vip) o;return id vip.id; //id一致则为返回为true}Overridepublic int hashCode() {return Objects.hash(id);}
}测试代码运行结果只存进去一个
4.2 LinkedHashSet
LinkedHashSet底层就是LinkedHashMap。所以底层是“哈希表双向链表”。LinkedHashSet集合存储元素特点有序不可重复。有序指的是存进去的顺序和取出的顺序一样。放进去的元素也需要重写hashCodeequals。
示例代码
package settest;import java.util.LinkedHashSet;
import java.util.Set;public class LinkedHashSetTest {public static void main(String[] args) {SetInteger set new LinkedHashSet();//有序不可重复set.add(200);set.add(200);set.add(200);set.add(10);set.add(2);set.add(3000);System.out.println(set);SetString set2 new LinkedHashSet();//有序不可重复set2.add(aaa);set2.add(aaa);set2.add(bbb);set2.add(ccc);set2.add(ddd);set2.add(eee);System.out.println(set2);}
}运行结果存入顺序和取出顺序一致 key为自定义类型重写hashCode和equals方法就不写了…
4.3 TreeSet
TreeSet底层就是TreeMap。所以底层也是红黑树。TreeSet集合存储元素特点有序不可重复。有序表示可排序。放在TreeSet集合中元素要想排序要么存储的元素实现Comparable接口要么在构造TreeSet集合的时候传一个Comparator比较器。不可重复放进去的元素也需要重写hashCodeequals。TreeSet中不能存放null。 示例代码Vip类如上
package settest;import java.util.Comparator;
import java.util.Set;
import java.util.TreeSet;public class TreeSetTest01 {public static void main(String[] args) {//创建TreeSet对象SetInteger set new TreeSet();//存入set.add(100);set.add(23);set.add(5);set.add(18);set.add(1);System.out.println(set);//创建TreeSet对象SetString set2 new TreeSet();//存入set2.add(abb);set2.add(bbb);set2.add(abc);set2.add(bba);set2.add(acb);System.out.println(set2);//创建存放自定义类型的TreeSet对象并传入比较器SetVip vips new TreeSet(new ComparatorVip() {Overridepublic int compare(Vip o1, Vip o2) {return o1.getId() - o2.getId(); //按id排序}});//创建Vip对象Vip vip1 new Vip(113,20,zhangsan);Vip vip2 new Vip(112,20,lisi);Vip vip3 new Vip(111,20,wangwu);//存入vips.add(vip1);vips.add(vip2);vips.add(vip3);System.out.println(vips);}
}运行结果有序输出
4.4 关于HashSet的面试题
有一个Student类
package settest;import java.util.Objects;public class Student {private String name;private int age;public Student() {}public Student(String name, int age) {this.name name;this.age age;}public String getName() {return name;}public void setName(String name) {this.name name;}public int getAge() {return age;}public void setAge(int age) {this.age age;}Overridepublic boolean equals(Object o) {if (this o) return true;if (o null || getClass() ! o.getClass()) return false;Student student (Student) o;return age student.age Objects.equals(name, student.name);}Overridepublic int hashCode() {return Objects.hash(name, age);}Overridepublic String toString() {return Student{ name name \ , age age };}
}阅读以下代码回答其中的问题
package settest;import java.util.HashSet;public class HashSetTest03 {public static void main(String[] args) {HashSetStudent set new HashSet();Student stu new Student(张三, 18);set.add(stu);set.add(new Student(李四, 21));stu.setName(王五);// 问题1请问是否删除了HashSet集合中的stu对象呢set.remove(stu);// 问题2添加以下Student对象是否成功set.add(new Student(王五, 18));// 问题3添加以下Student对象是否成功set.add(new Student(张三, 18));}
}分析与运行结果
package settest;import java.util.HashSet;public class HashSetTest03 {public static void main(String[] args) {//这种题目需要头脑清醒一步一步分析//创建HashSet对象HashSetStudent set new HashSet();//创建Student对象stuStudent stu new Student(张三, 18);//存入set.add(stu);//存入新的对象set.add(new Student(李四, 21));//修改stu对象的name由于set中存放的是stu的地址所以set中对应的stu的name也修改了但是set中stu对应节点还是采用的之前 张三和年龄18 生成的哈希值stu.setName(王五);System.out.println(set);// 问题1请问是否删除了HashSet集合中的stu对象呢//不能删除remove寻找时使用的是修改后的 王五 和年龄18 的哈希值 进行寻找而stu节点还是采用的之前 张三和年龄18 生成的哈希值并不一致所以并不能找到set.remove(stu);System.out.println(set);// 问题2添加以下Student对象是否成功//添加成功同上存入时是按 王五 和年龄18 生成的哈希值不会与当前哈希值产生冲突可以直接存入set.add(new Student(王五, 18));System.out.println(set);// 问题3添加以下Student对象是否成功//添加成功存入时会与stu节点产生哈希冲突但是由于name不一样equals返回为false所以判定并不是相同节点可以尾插法存入set.add(new Student(张三, 18));System.out.println(set);}
} 5.Collections工具类
测试几个针对List集合的常用方法 ①排序方法sort ②混排打乱顺序shuffle ③反转reverse ④替换所有元素fill
package collectionstest;import java.util.ArrayList;
import java.util.Collections;
import java.util.List;/*** 测试集合工具类java.util.Collections*/
public class CollectionsTest {public static void main(String[] args) {//1.sort方法专门针对List集合提供的一个sort方法ListInteger list new ArrayList();list.add(100);list.add(12);list.add(8);list.add(7);list.add(10);System.out.println(list);Collections.sort(list);System.out.println(list);System.out.println();//如果List集合中的元素是自定义类型的若需要使用sort排序// 则该自定义类型需要实现Comparable接口提供比较规则// 或者排序时传入一个Comparator比较器ListPerson personList new ArrayList();Person p1 new Person(21);Person p2 new Person(11);Person p3 new Person(18);Person p4 new Person(20);personList.add(p1);personList.add(p2);personList.add(p3);personList.add(p4);System.out.println(personList);Collections.sort(personList);System.out.println(personList);System.out.println();//2.shuffle方法打乱顺序System.out.println(list);Collections.shuffle(list);System.out.println(list);System.out.println();//3.reverse方法 反转List集合中的元素System.out.println(personList);Collections.reverse(personList);System.out.println(personList);System.out.println();//4.fill替换所有元素System.out.println(list);Collections.fill(list,null);System.out.println(list);}
}class Person implements ComparablePerson{private int age;public Person() {}public Person(int age) {this.age age;}public int getAge() {return age;}public void setAge(int age) {this.age age;}Overridepublic String toString() {return Person{ age age };}Overridepublic int compareTo(Person o) {return this.age - o.age;}
}运行结果
