六安网站建设费用,wordpress内置rest api,高端h5手机网站设计案例,邯郸专业做网站目录
Java集合#xff08;三#xff09;
Java双列集合体系介绍
HashMap类
HashMap类介绍
HashMap类常用方法
HashMap类元素遍历
LinkedHashMap类
LinkedHashMap类介绍
LinkedHashMap类常用方法
LinkedHashMap类元素遍历
Map接口自定义类型去重的方式
Set接口和Ma…目录
Java集合三
Java双列集合体系介绍
HashMap类
HashMap类介绍
HashMap类常用方法
HashMap类元素遍历
LinkedHashMap类
LinkedHashMap类介绍
LinkedHashMap类常用方法
LinkedHashMap类元素遍历
Map接口自定义类型去重的方式
Set接口和Map接口无索引操作原因分析
HashMap无序但LinkedHashMap有序原因分析
Map练习案例
案例1统计字符串每一个字符出现的次数
案例2斗地主案例HashMap版本
哈希表结构存储过程分析
哈希表结构源码分析
使用无参构造创建HashMap对象
第一次插入元素
使用有参构造创建HashMap对象
哈希值相同时比较源码
TreeSet类
TreeMap类
HashTable与Vector
Properties类
Properties类介绍
Properties类特有方法 Java集合三
Java双列集合体系介绍
在Java中双列集合的顶级接口是Map接口其下有下面的分类
HashMap类LinkedHashMap类TreeMap类HashTable类Properties类
其体系及特点如下图所示 HashMap类
HashMap类介绍
HashMap类是Map接口的实现类其特点如下
key唯一但value不唯一插入顺序与存储顺序不一定相同没有索引方式操作元素的方法线程不安全可以存null值
对应的数据结构为哈希表
需要注意如果出现 key重复会保留最后一个键值对的 value即「发生 value覆盖」 HashMap类常用方法
V put(K key, V value)向HashMap中插入元素返回被参数value覆盖的valueV remove(Object key)根据key值移除HashMap中指定的元素返回被删除的键值对对应的valueV get(Object key)根据key值获取对应的valueboolean containsKey(Object key)判断HashMap中是否还有指定key元素CollectionV values()获取HashMap中所有的value将其值存储到单列集合中
基本使用如下
public class Test01 {public static void main(String[] args) {HashMapString, String map new HashMap();// 1. V put(K key, V value)向HashMap中插入元素返回被参数value覆盖的valueSystem.out.println(map.put(老大, 张三));System.out.println(map.put(老二, 李四));System.out.println(map.put(老三, 王五));// 2. V remove(Object key)根据key值移除HashMap中指定的元素返回被删除的键值对对应的valueSystem.out.println(map.remove(老二));// 3. V get(Object key)根据key值获取对应的valueSystem.out.println(map.get(老大));// 4. boolean containsKey(Object key)判断HashMap中是否还有指定key元素System.out.println(map.containsKey(老大));// 5. CollectionV values()获取HashMap中所有的value将其值存储到单列集合中CollectionString values map.values();for (String value : values) {System.out.println(value);}}
}
HashMap类元素遍历
HashMap遍历方式有以下两种
通过key值获取到对应的value通过SetK keySet()方法将获取到的key存入到Set中再使用Set集合的迭代器获取对应的value通过SetMap.EntryK,V entrySet()获取到HashMap中的键值对存入到Set中再通过Map的内部静态接口Map.Entry中的getKey方法和getValue方法分别获取到Map中对应的键值对
基本使用如下
public class Test02 {public static void main(String[] args) {HashMapString, String map new HashMap();map.put(老大, 张三);map.put(老二, 李四);map.put(老三, 王五);// 根据key获取value遍历SetString strings map.keySet();for (String string : strings) {System.out.println(stringmap.get(string));}System.out.println();// 使用entrySet遍历SetMap.EntryString, String entries map.entrySet();for (Map.EntryString, String entry : entries) {System.out.println(entry.getKey()entry.getValue());}}
}
LinkedHashMap类
LinkedHashMap类介绍
key唯一但value不唯一插入顺序与存储顺序相同没有索引方式操作元素的方法线程不安全可以存null值
对应的数据结构为哈希表双向链表
LinkedHashMap类常用方法
因为LinkedHashMap类继承自HashMap类所以常用方法与HashMap基本一致
V put(K key, V value)向HashMap中插入元素返回被参数value覆盖的valueV remove(Object key)根据key值移除HashMap中指定的元素返回被删除的键值对对应的valueV get(Object key)根据key值获取对应的valueboolean containsKey(Object key)判断HashMap中是否还有指定key元素CollectionV values()获取HashMap中所有的value将其值存储到单列集合中
基本使用如下
public class Test03 {public static void main(String[] args) {LinkedHashMapString, String map new LinkedHashMap();// 1. V put(K key, V value)向HashMap中插入元素返回被参数value覆盖的valueSystem.out.println(map.put(老大, 张三));System.out.println(map.put(老二, 李四));System.out.println(map.put(老三, 王五));// 2. V remove(Object key)根据key值移除HashMap中指定的元素返回被删除的键值对对应的valueSystem.out.println(map.remove(老二));// 3. V get(Object key)根据key值获取对应的valueSystem.out.println(map.get(老大));// 4. boolean containsKey(Object key)判断HashMap中是否还有指定key元素System.out.println(map.containsKey(老大));// 5. CollectionV values()获取HashMap中所有的value将其值存储到单列集合中CollectionString values map.values();for (String value : values) {System.out.println(value);}}
}
LinkedHashMap类元素遍历
遍历方式与HashMap类一致
HashMap遍历方式有以下两种
通过key值获取到对应的value通过SetK keySet()方法将获取到的key存入到Set中再使用Set集合的迭代器获取对应的value通过SetMap.EntryK,V entrySet()获取到HashMap中的键值对存入到Set中再通过Map的内部静态接口Map.Entry中的getKey方法和getValue方法分别获取到Map中对应的键值对
public class Test04 {public static void main(String[] args) {LinkedHashMapString, String linkedHashMap new LinkedHashMap();linkedHashMap.put(老大, 张三);linkedHashMap.put(老二, 李四);linkedHashMap.put(老三, 王五);// 根据key获取value遍历SetString strings linkedHashMap.keySet();for (String string : strings) {System.out.println(stringlinkedHashMap.get(string));}System.out.println();// 使用entrySet遍历SetMap.EntryString, String entries linkedHashMap.entrySet();for (Map.EntryString, String entry : entries) {System.out.println(entry.getKey()entry.getValue());}}
}
Map接口自定义类型去重的方式
以下面的自定义类为例
public class Person {private int age;private String name;public Person(int age, String name) {this.age age;this.name name;}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;}
}
以下面的测试为例
public class Test05 {public static void main(String[] args) {LinkedHashMapPerson, String personHashMap new LinkedHashMap();personHashMap.put(new Person(18, 张三), 老大);personHashMap.put(new Person(19, 李四), 老二);personHashMap.put(new Person(20, 王五), 老三);personHashMap.put(new Person(20, 王五), 老三);// 遍历SetMap.EntryPerson, String entries personHashMap.entrySet();for (Map.EntryPerson, String entry : entries) {System.out.println(entry.getKey()entry.getValue());}}
}
前面在Set部分提到HashSet的去重方式
先计算元素的哈希值重写hashCode方法再比较内容重写equals方法先比较哈希值如果哈希值不一样存入集合中如果哈希值一样,再比较内容 如果哈希值一样内容不一样直接存入集合如果哈希值一样内容也一样去重复内容留一个存入集合
在Map接口中也是同样的方式去重所以对于自定义类型来说一样需要重写equals和hashCode方法
如果Person类没有重写hashCode和equals方法此时Person对象比较方式是按照地址比较所以对于第三个元素和第四个元素来说是两个元素此时输出结果就会是下面的情况
Person{age18, name张三}老大
Person{age19, name李四}老二
Person{age20, name王五}老三
Person{age20, name王五}老三
而重写了hashCode和equals方法后就可以避免上面的问题
Person{age18, name张三}老大
Person{age19, name李四}老二
Person{age20, name王五}老三
Set接口和Map接口无索引操作原因分析
哈希表中虽然有数组但是Set和Map却没有索引因为存数据的时候有可能在同一个索引下形成链表如果1索引上有一条链表根据Set和Map的遍历方式「依次遍历每一条链表」那么要是按照索引1获取此时就会遇到多个元素无法确切知道哪一个元素是需要的所以就取消了按照索引操作的机制 HashMap无序但LinkedHashMap有序原因分析
HashMap底层的哈希表是数组单向链表红黑树因为单向链表只有一个节点引用执行下一个节点此时只能保证当前链表上的节点元素可能与插入顺序相同但是如果使用双向链表就可以解决这个问题过程如下 Map练习案例
案例1统计字符串每一个字符出现的次数
统计字符串abcdsaasdhubsdiwb中每一个字符出现的次数
思路
遍历字符串依次插入HashMapString, Integer或者LinkedHashMapString, Integer中这个过程中会出现两种情况
字符不存在与HashMap中属于第一次插入将计数器记为1字符存在于HashMap中代表非第一次插入将计数器加1重新插入到HashMap中
代码实例
public class Test01 {public static void main(String[] args) {String str abcdsaasdhubsdiwb;HashMapCharacter, Integer counter new HashMap();// 将字符串存入数组中注意存入的是字符而不是字符对应的ASCII码char[] chars str.toCharArray();for (char c : chars) {// 遍历HashMap如果不存在字符就插入存在就将value值加1if (!counter.containsKey(c)) {counter.put(c, 1);} else {counter.put(c, counter.get(c) 1);}}// 打印结果SetCharacter characters counter.keySet();for (Character character : characters) {System.out.println(character counter.get(character));}}
}
案例2斗地主案例HashMap版本
思路
使用HashMap存储每一张牌包括值和样式key存储牌的序号从0开始value存储牌面使用前面同样的方式组合牌并存入HashMap中存储过程中每存一张牌key位置的数值加1。为了保证可以打乱牌需要将牌面对应的序号存入一个单列容器再调用shuffle方法。打乱后的牌通过序号从HashMap中取出此时遍历HashMap通过key获取value即可
其中有些一小部分可以适当修改例如每一个玩家的牌面按照序号排序查看玩家牌可以通过调用一个函数完成相应的行为等
此处当 key是有序数值会出现插入顺序与存储数据相同 示例代码
public class Test_Poker02 {public static void main(String[] args) {// 创建花色String[] color 黑桃-红心-梅花-方块.split(-);// 创建号牌String[] number 2-3-4-5-6-7-8-9-10-J-Q-K-A.split(-);HashMapInteger, String count_poker new HashMapInteger, String();int key 2;// 从2开始保留两张牌给大王和小王// 组合牌for (String c : color) {for (String n : number) {// 插入到HashMap中count_poker.put(key, cn);}}count_poker.put(0, 大王);count_poker.put(1, 小王);// 创建一个ArrayList专门存牌号便于打乱牌面ArrayListInteger count new ArrayList();SetInteger integers count_poker.keySet();for (Integer integer : integers) {count.add(integer);}// 打乱牌号从而实现打乱牌面Collections.shuffle(count);// 创建玩家ArrayListInteger player1 new ArrayList();ArrayListInteger player2 new ArrayList();ArrayListInteger player3 new ArrayList();// 创建底牌ArrayListInteger last new ArrayList();// 发牌for (int i 0; i count.size(); i) {if(i 51) {last.add(count.get(i));} else if(i % 3 0) {player1.add(count.get(i));} else if(i % 3 1) {player2.add(count.get(i));} else if(i % 3 2) {player3.add(count.get(i));}}// 对玩家的牌进行排序Collections.sort(player1);Collections.sort(player2);Collections.sort(player3);// 显示玩家牌show(玩家1, player1, count_poker);show(玩家2, player2, count_poker);show(玩家3, player3, count_poker);show(底牌, last, count_poker);}public static void show(String name, ArrayListInteger any, HashMapInteger, String poker) {System.out.print(name [ );for (Integer i : any) {System.out.print(poker.get(i) );}System.out.println(]);}
}
哈希表结构存储过程分析
HashMap底层的数据结构是哈希表但是不同的JDK版本实现哈希表的方式有所不同
JDK7时的哈希表数组单链表JDK8及之后的哈希表数组链表红黑树
以JDK8及之后的版本为例存储过程如下
先计算哈希值此处哈希值会经过两部分计算1. 对象内部的hashCode方法计算一次 2. HashMap底层再计算一次如果哈希值不一样或者哈希值一样但内容不一样哈希冲突直接存入HashMap如果哈希值一样且内容也一样则发生value覆盖现象
在Java中HashMap在实例化对象时如果不指定大小则默认会开辟一个长度为16的数组。但是该数组与ArrayList一样只有在第一次插入数据时才会开辟容量
而哈希表扩容需要判断加载因子loadfactor默认负载因子loadfactor大小为0.75如果插入过程中加载因子loadfactor超过了0.75就会发生扩容
存储数据的过程中如果出现哈希值一样内容不一样的情况就会在数组同一个索引位置形成一个链表依次链接新节点和旧节点。如果链表的长度超过了8个节点并且数组的长度大于等于64此时链表就会转换为红黑树同样如果后续删除节点导致元素个数小于等于6红黑树就会降为链表
哈希表结构源码分析
查看源码时可能会使用到的常量
static final float DEFAULT_LOAD_FACTOR 0.75f; // 默认加载因子
static final int TREEIFY_THRESHOLD 8; // 转化为红黑树的节点个数
static final int MIN_TREEIFY_CAPACITY 64; // 转化为红黑树时最小的数组长度
static final int UNTREEIFY_THRESHOLD 6; // 红黑树退化为链表的节点个数
static final int MAXIMUM_CAPACITY 1 30; // 最大容量
static final int DEFAULT_INITIAL_CAPACITY 1 4; // 最小容量
查看源码时会看到的底层节点结构
static class NodeK,V implements Map.EntryK,V {final int hash;final K key;V value;NodeK,V next;Node(int hash, K key, V value, NodeK,V next) {this.hash hash;this.key key;this.value value;this.next next;}// ...
}
使用无参构造创建HashMap对象
测试代码
HashMapString, String map new HashMap();
对应源码
public HashMap() {this.loadFactor DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
第一次插入元素
测试代码
HashMapString, String map new HashMap();
map.put(1, 张三);
对应源码
public V put(K key, V value) {return putVal(hash(key), key, value, false, true);
}final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {NodeK,V[] tab; NodeK,V p; int n, i;if ((tab table) null || (n tab.length) 0)n (tab resize()).length;if ((p tab[i (n - 1) hash]) null)tab[i] newNode(hash, key, value, null);// ...modCount;if (size threshold)resize();// ...return null;
}// 创建新节点
NodeK,V newNode(int hash, K key, V value, NodeK,V next) {return new Node(hash, key, value, next);
}// 扩容
final NodeK,V[] resize() {NodeK,V[] oldTab table;int oldCap (oldTab null) ? 0 : oldTab.length;int oldThr threshold;int newCap, newThr 0;if (oldCap 0) {// ... }else if (oldThr 0)// ...else { newCap DEFAULT_INITIAL_CAPACITY;newThr (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);}// ...threshold newThr;SuppressWarnings({rawtypes,unchecked})NodeK,V[] newTab (NodeK,V[])new Node[newCap];table newTab;// ...return newTab;
} threshold代表扩容边界是 HashMap中的成员变量由容量和负载因子相乘计算得到 在上面的代码中插入数据调用put方法底层会调用putVal方法进入putVal后首先会判断当前表是否为空而此时因为是第一次插入元素元素还没有进入表中当前表为空所以会走第一个if语句进入内部执行n (tab resize()).length;会执行resize方法为当前的tab扩容
进入resize方法中当前的成员table即为HashMap底层的哈希表因为不存在元素所以为空从而oldTab也为空执行后面的代码后oldCap和oldThr均为0直接进入else语句中将newCap置为16同时将newThr赋值为12执行完毕后将成员threshold更新为newThr的值将新容量16作为数组长度创建一个新的数组newTab将newTab给成员变量table返回给调用处继续执行
此处需要注意对于 NodeK,V[] newTab (NodeK,V[])new Node[newCap];来说因为Java不支持创建泛型数组所以先创建原始类型数组再通过强制转换将其转换为泛型数组 回到调用处n (tab resize()).length;此时tab即为成员变量table的值获取其长度即为16。接着执行第二个if语句此处的i (n - 1) hash用于计算哈希表的映射位置即数组索引进入if语句创建节点并插入到指定索引位置改变size并比较是否超过threshold此处未超过不用扩容改变并发修改控制因子返回被覆盖的null
使用有参构造创建HashMap对象
测试代码
HashMapString, String map1 new HashMap(5)
对应源码
public HashMap(int initialCapacity) {this(initialCapacity, DEFAULT_LOAD_FACTOR);
}public HashMap(int initialCapacity, float loadFactor) {if (initialCapacity 0)throw new IllegalArgumentException(Illegal initial capacity: initialCapacity);if (initialCapacity MAXIMUM_CAPACITY)initialCapacity MAXIMUM_CAPACITY;// ... this.loadFactor loadFactor;this.threshold tableSizeFor(initialCapacity);
}static final int tableSizeFor(int cap) {int n cap - 1;n | n 1;n | n 2;n | n 4;n | n 8;n | n 16;return (n 0) ? 1 : (n MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n 1;
}
当执行有一个参数的构造时底层调用内部的有两个参数的构造第一个参数即为初始容量大小第二个参数传递默认的加载因子
在有两个参数的构造中首先判断初始容量initialCapacity是否小于0如果小于则抛出异常再判断初始容量initialCapacity是否大于最大值如果大于则修正为最大值。
在执行完所有判断后将加载因子赋值给成员变量loadfactor再根据初始容量计算扩容前最大的容量
哈希值相同时比较源码
NodeK,V e; K k;
if (p.hash hash ((k p.key) key || (key ! null key.equals(k))))e p;
首先比较哈希值如果哈希值相同则比较key对应的value为了防止出现key为空导致的空指针问题先判断key不为空再比较key
上面过程即「先比较哈希值相同再比较内容」
TreeSet类
TreeSet类是Set接口的实现类其有如下的特点
默认会对插入的数据进行排序没有索引的方式操作元素不可以存null值相同元素不重复出现线程不安全
底层数据结构为红黑树
常用构造方法
无参构造方法TreeSet()默认按照ASCII码对元素进行比较使用传递比较器作为参数的有参构造方法TreeSet(Comparator? super E comparator)
基本使用如下
// 自定义类
public class Person {private String name;private int age;public Person() {}public Person(String name, int age) {super();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 Person{ name name \ , age age };}Overridepublic boolean equals(Object o) {if (this o) return true;if (o null || getClass() ! o.getClass()) return false;Person person (Person) o;return age person.age Objects.equals(name, person.name);}Overridepublic int hashCode() {return Objects.hash(name, age);}
}// 测试
public class Test02 {public static void main(String[] args) {TreeSetString set new TreeSet();set.add(1);set.add(112);set.add(13);// 使用增强for遍历for (String s : set) {System.out.println(s);}System.out.println();TreeSetPerson people new TreeSet(new ComparatorPerson() {Overridepublic int compare(Person o1, Person o2) {return o1.getAge() - o2.getAge();}});people.add(new Person(张三, 23));people.add(new Person(李四, 24));people.add(new Person(王五, 25));// 使用增强for遍历for (Person person : people) {System.out.println(person);}}
}
TreeMap类
TreeMap类是Map接口的实现类其特点如下
默认会对插入的数据进行排序没有索引的方式操作元素key唯一value不唯一不可以存null值相同元素不重复出现线程不安全
底层数据结构为红黑树
常用构造方法
无参构造方法TreeMap()默认按照ASCII码对元素进行比较使用传递比较器作为参数的有参构造方法TreeMap(Comparator? super E comparator)
// 自定义类
public class Person {private String name;private int age;public Person() {}public Person(String name, int age) {super();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 Person{ name name \ , age age };}Overridepublic boolean equals(Object o) {if (this o) return true;if (o null || getClass() ! o.getClass()) return false;Person person (Person) o;return age person.age Objects.equals(name, person.name);}Overridepublic int hashCode() {return Objects.hash(name, age);}
}// 测试
public class Test02 {public static void main(String[] args) {TreeSetString set new TreeSet();set.add(1);set.add(112);set.add(13);// 使用增强for遍历for (String s : set) {System.out.println(s);}System.out.println();TreeSetPerson people new TreeSet(new ComparatorPerson() {Overridepublic int compare(Person o1, Person o2) {return o1.getAge() - o2.getAge();}});people.add(new Person(张三, 23));people.add(new Person(李四, 24));people.add(new Person(王五, 25));// 使用增强for遍历for (Person person : people) {System.out.println(person);}}
}
HashTable与Vector
HashTable类是Map接口的实现类其特点如下
key唯一value可重复插入顺序与存储顺序不一定相同没有索引的方式操作元素线程安全不能存储null值
底层数据结构哈希表
Vector类是Collection接口的实现类其特点如下
元素插入顺序与存储顺序相同有索引的方式操作元素元素可以重复线程安全
底层数据结构数组
因为HashTable和Vector现在已经不经常使用了所以使用及特点自行了解即可
Properties类
Properties类介绍
Properties类是HashTable类的子类其特点如下
key唯一value可重复插入顺序与存储顺序不一定相同没有索引的方式操作元素线程安全不能存储null值Properties类不是泛型类默认元素是String类型
底层数据结构哈希表
Properties类特有方法
常用方法与HashMap等类似此处主要考虑特有方法
Object setProperty(String key, String value)存键值对String getProperty(String key)根据key获取对应的valueSetString stringPropertyNames()将所有key对应的value存储到Set中类似于HashMap中的KeySet方法void load(InputStream inStream)将流中的数据加载到Properties类中具体见IO流部分
基本使用如下
public class Test08 {public static void main(String[] args) {Properties properties new Properties();//Object setProperty(String key, String value)properties.setProperty(username,root);properties.setProperty(password,1234);System.out.println(properties);//String getProperty(String key)System.out.println(properties.getProperty(username));//SetString stringPropertyNames()SetString set properties.stringPropertyNames();for (String key : set) {System.out.println(properties.getProperty(key));}}
}
