欢迎大家来到IT世界,在知识的湖畔探索吧!
一、双例集合
1. Map 接口介绍
Map 接口特点：Map 接口定义了双例集合的存储特征，它并不是 Collection 接口的子接口。双例集合的存储特征是以 key 与 value 结构为单位进行存储。体现的是数学中的函数 y=f(x)感念。
Map 与 Collecton 的区别：
1.Collection 中的容器，元素是孤立存在的（理解为单身），向集合中存储元素采用一个个元素的方式存储。
2.Map 中的容器，元素是成对存在的(理解为现代社会的夫妻)。每个元素由键与值两部分组成，通过键可以找对所对应的值。
3.Collection 中的容器称为单列集合，Map 中的容器称为双列集合。
4.Map 中的集合不能包含重复的键，值可以重复；每个键只能对应一个值。
5.Map 中常用的容器为 HashMap，TreeMap 等。
|
Map的常用方法 |
|
|
方法 |
说明 |
|
V put(K key,V value) |
把key与value添加到Map集合中 |
|
void putAll(Map m) |
从指定Map中将所有映射关系复制到此Map中 |
|
V remove(Object key) |
删除key对应的value |
|
V get(Object key) |
根据指定的key，获取对应的value |
|
boolean containsKey(Object key) |
判断容器中是否包含指定的key |
|
boolean containsValue(Object value) |
判断容器中是否包含指定的value |
|
Set keySet() |
获取Map集合中所有的key，存储到Set集合中 |
|
Set<Map.Entry<K,V>> entrySet() |
返回一个Set基于Map.Entry类型包含Map中所有映射。 |
|
void clear() |
删除Map中所有的映射 |
2. HashMap 容器类
HashMap 是 Map 接口的接口实现类，它采用哈希算法实现，是 Map 接口最常用的实现类。 由于底层采用了哈希表存储数据，所以要求键不能重复，如果发生重复，新的值会替换旧的值。 HashMap 在查找、删除、修改方面都有非常高的效率。
2.1 添加元素：
package cn.pxy.test;
import java.util.HashMap;
import java.util.Map;
public class HashMapTest {
public static void main(String[] args) {
//实例化HashMap容器
Map<String,String> map=new HashMap<>();
//输入元素
map.put("a","A");
System.out.println(map.get("a"));
map.put("a","B");
String value=map.get("a");
System.out.println(value);
}
}欢迎大家来到IT世界,在知识的湖畔探索吧!
运行结果：
2.2 获取元素方式：
方式一：通过get获取
欢迎大家来到IT世界,在知识的湖畔探索吧!String value=map.get("a");
Syetem.out.println(value);
方式二：通过keySet获取
//获取 HashMap 容器中所有的元素，可以使用 keySet 方法与 get 方法一并完成。
package cn.pxy.test;
import java.util.HashMap;
import java.util.Map;
import java.util.Set;
public class HashMapTest {
public static void main(String[] args) {
//实例化HashMap容器
Map<String,String> map=new HashMap<>();
//输入元素
map.put("a","A");
System.out.println(map.get("a"));
map.put("a","B");
String value=map.get("a");
System.out.println(value);
map.put("b","C");
map.put("c", "D");
//获取 HashMap 容器中所有的元素，可以使用 keySet 方法与 get 方法一并完成。
//获取所有的key
Set<String> keys=map.keySet();
for(String key:keys) {
String value1=map.get(key);
System.out.println(key+"-----"+value1);
}
}
}运行效果：
方式三：通过 entrySet 方法获取 Map.Entry 类型获取元素
欢迎大家来到IT世界,在知识的湖畔探索吧!package cn.pxy.test;
import java.util.HashMap;
import java.util.Map;
import java.util.Set;
public class HashMapTest {
public static void main(String[] args) {
//实例化HashMap容器
Map<String,String> map=new HashMap<>();
//输入元素
map.put("a","A");
System.out.println(map.get("a"));
map.put("a","B");
String value=map.get("a");
System.out.println(value);
map.put("b","C");
map.put("c", "D");
Set<String> keys=map.keySet();
for(String key:keys) {
String value1=map.get(key);
System.out.println(key+"-----"+value1);
}
System.out.println("********");
//通过 entrySet 方法获取 Map.Entry 类型获取元素
//返回一个 Set 基于 Map.Entry 类型包含 Map 中所有映射
Set<Map.Entry<String,String>> entrySet = map.entrySet();
for(Map.Entry<String,String> entry:entrySet){
String key = entry.getKey();
String v = entry.getValue();
System.out.println(key+" ---------- "+v);
}
}
}
运行效果：
2.3 Map 容器的并集操作：
package cn.pxy.test;
import java.util.HashMap;
import java.util.Map;
import java.util.Set;
public class HashMapTest {
public static void main(String[] args) {
//实例化HashMap容器
Map<String,String> map=new HashMap<>();
//输入元素;若key相同，则value被覆盖
System.out.println("***输入元素;若key相同，则value被覆盖**");
map.put("a","A");
System.out.println(map.get("a"));
map.put("a","B");
//通过get获取元素
String value=map.get("a");
System.out.println(value);
//通过keySet获取元素
System.out.println("***通过keySet获取元素***");
map.put("b","C");
map.put("c", "D");
Set<String> keys=map.keySet();
for(String key:keys) {
String value1=map.get(key);
System.out.println(key+"-----"+value1);
}
//通过 entrySet 方法获取 Map.Entry 类型获取元素
//返回一个 Set 基于 Map.Entry 类型包含 Map 中所有映射
System.out.println("***通过 entrySet 方法获取 Map.Entry 类型获取元素***");
Set<Map.Entry<String,String>> entrySet = map.entrySet();
for(Map.Entry<String,String> entry:entrySet){
String key = entry.getKey();
String v = entry.getValue();
System.out.println(key+" ---------- "+v);
}
//并集操作
System.out.println("*****并集操作*****");
//实例化Map容器
Map<String,String> map2=new HashMap<>();
map2.put("e", "cc");
map2.put("f", "dd");
//并集操作
map2.putAll(map);
Set<String> keys2=map2.keySet();
for(String key:keys2) {
String value2=map2.get(key);
System.out.println("Key:"+key+"----"+" Value:"+value2);
}
}
}运行结果：
2.4 删除元素：
package cn.pxy.test;
import java.util.HashMap;
import java.util.Map;
import java.util.Set;
public class HashMapTest {
public static void main(String[] args) {
//实例化HashMap容器
Map<String,String> map=new HashMap<>();
//输入元素;若key相同，则value被覆盖
System.out.println("***输入元素;若key相同，则value被覆盖**");
map.put("a","A");
System.out.println(map.get("a"));
map.put("a","B");
//通过get获取元素
String value=map.get("a");
System.out.println(value);
//通过keySet获取元素
System.out.println("***通过keySet获取元素***");
map.put("b","C");
map.put("c", "D");
Set<String> keys=map.keySet();
for(String key:keys) {
String value1=map.get(key);
System.out.println(key+"-----"+value1);
}
//通过 entrySet 方法获取 Map.Entry 类型获取元素
//返回一个 Set 基于 Map.Entry 类型包含 Map 中所有映射
System.out.println("***通过 entrySet 方法获取 Map.Entry 类型获取元素***");
Set<Map.Entry<String,String>> entrySet = map.entrySet();
for(Map.Entry<String,String> entry:entrySet){
String key = entry.getKey();
String v = entry.getValue();
System.out.println(key+" ---------- "+v);
}
//并集操作
System.out.println("*****并集操作*****");
//实例化Map容器
Map<String,String> map2=new HashMap<>();
map2.put("e", "cc");
map2.put("f", "dd");
//并集操作
map2.putAll(map);
Set<String> keys2=map2.keySet();
for(String key:keys2) {
String value2=map2.get(key);
System.out.println("Key:"+key+"----"+" Value:"+value2);
}
//删除元素
System.out.println("***删除元素***");
String v=map2.remove("e");//删除 e 对应的 value
System.out.println(v);
Set<String> keys3=map2.keySet();
for(String key:keys3) {
String value3=map2.get(key);
System.out.println("Key:"+key+" Value:"+value3);
}
}
}运行结果：
2.5 判断 key 或 value 是否存在：
package cn.pxy.test;
import java.util.HashMap;
import java.util.Map;
import java.util.Set;
public class HashMapTest {
public static void main(String[] args) {
//实例化HashMap容器
Map<String,String> map=new HashMap<>();
//输入元素;若key相同，则value被覆盖
System.out.println("***输入元素;若key相同，则value被覆盖**");
map.put("a","A");
System.out.println(map.get("a"));
map.put("a","B");
//通过get获取元素
String value=map.get("a");
System.out.println(value);
//通过keySet获取元素
System.out.println("***通过keySet获取元素***");
map.put("b","C");
map.put("c", "D");
Set<String> keys=map.keySet();
for(String key:keys) {
String value1=map.get(key);
System.out.println(key+"-----"+value1);
}
//通过 entrySet 方法获取 Map.Entry 类型获取元素
//返回一个 Set 基于 Map.Entry 类型包含 Map 中所有映射
System.out.println("***通过 entrySet 方法获取 Map.Entry 类型获取元素***");
Set<Map.Entry<String,String>> entrySet = map.entrySet();
for(Map.Entry<String,String> entry:entrySet){
String key = entry.getKey();
String v = entry.getValue();
System.out.println(key+" ---------- "+v);
}
//并集操作
System.out.println("*****并集操作*****");
//实例化Map容器
Map<String,String> map2=new HashMap<>();
map2.put("e", "cc");
map2.put("f", "dd");
//并集操作
map2.putAll(map);
Set<String> keys2=map2.keySet();
for(String key:keys2) {
String value2=map2.get(key);
System.out.println("Key:"+key+"----"+" Value:"+value2);
}
//删除元素
System.out.println("***删除元素***");
String v=map2.remove("e");//删除 e 对应的 value
System.out.println(v);
Set<String> keys3=map2.keySet();
for(String key:keys3) {
String value3=map2.get(key);
System.out.println("Key:"+key+" Value:"+value3);
}
System.out.println("****判断key或value是否存在****");
//判断Key是否存在
boolean flag=map2.containsKey("a");
System.out.println(flag);
//判断value是否存在
boolean flag2=map2.containsValue("kk");
System.out.println(flag2);
}
}运行结果：
2.6 HashMap 的底层源码分析：
底层存储：HashMap 底层实现采用了哈希表，这是一种非常重要的数据结构。对于我们以后理解很多技术都非常有帮助，因此，非常有必要让详细的理解。
数据结构中由数组和链表来实现对数据的存储，他们各有特点：
(1) 数组：占用空间连续。 寻址容易，查询速度快。但是，增加和删除效率非常低。
(2) 链表：占用空间不连续。 寻址困难，查询速度慢。但是，增加和删除效率非常高。
哈希表结合了数组和链表的优点（即查询快，增删效率也高），它的本质就是“数组+链表”。
成员变量：
/**
* The default initial capacity - MUST be a power of two.
*/
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.
*/
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.
*/
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.
*/
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;
/**
* The number of key-value mappings contained in this map.
*/
transient int size;
/**
* The table, initialized on first use, and resized as
* necessary. When allocated, length is always a power of two.
* (We also tolerate length zero in some operations to allow
* bootstrapping mechanics that are currently not needed.)
*/
transient Node<K,V>[] table;HashMap 中存储元素的节点类型：
Node类：
/**
* Basic hash bin node, used for most entries. (See below for
* TreeNode subclass, and in LinkedHashMap for its Entry subclass.)
*/
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;
}
public final K getKey() { return key; }
public final V getValue() { return value; }
public final String toString() { return key + "=" + value; }
public final int hashCode() {
return Objects.hashCode(key) ^ Objects.hashCode(value);
}
public final V setValue(V newValue) {
V oldValue = value;
value = newValue;
return oldValue;
}
public final boolean equals(Object o) {
if (o == this)
return true;
if (o instanceof Map.Entry) {
Map.Entry<?,?> e = (Map.Entry<?,?>)o;
if (Objects.equals(key, e.getKey()) &&
Objects.equals(value, e.getValue()))
return true;
}
return false;
}
}TreeNode类：
/**
* Entry for Tree bins. Extends LinkedHashMap.Entry (which in turn
* extends Node) so can be used as extension of either regular or
* linked node.
*/
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
TreeNode<K,V> parent; // red-black tree links
TreeNode<K,V> left;
TreeNode<K,V> right;
TreeNode<K,V> prev; // needed to unlink next upon deletion
boolean red;
TreeNode(int hash, K key, V val, Node<K,V> next) {
super(hash, key, val, next);
}
/**
* Returns root of tree containing this node.
*/
final TreeNode<K,V> root() {
for (TreeNode<K,V> r = this, p;;) {
if ((p = r.parent) == null)
return r;
r = p;
}
}继承关系：
数组初始化：
在 JDK1.8 的 HashMap 中对于数组的初始化采用的是延迟初始化方式。通过 resize 方法实现初始化处理。resize 方法既实现数组初始化，也实现数组扩容处理。
/**
* Initializes or doubles table size. If null, allocates in
* accord with initial capacity target held in field threshold.
* Otherwise, because we are using power-of-two expansion, the
* elements from each bin must either stay at same index, or move
* with a power of two offset in the new table.
*
* @return the table
*/
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
if (oldCap > 0) {
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // preserve order
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}计算 Hash 值：
(1) 获得 key 对象的 hashcode
首先调用 key 对象的 hashcode()方法，获得 key 的 hashcode 值。
(2) 根据 hashcode 计算出 hash 值(要求在[0, 数组长度-1]区间)
hashcode 是一个整数，我们需要将它转化成[0, 数组长度-1]的范围。我们要求转化后的 hash 值尽量均匀地分布在[0,数组长度-1]这个区间，减少“hash 冲突”
i. 一种极端简单和低下的算法是：
hash 值 = hashcode/hashcode;
也就是说，hash 值总是 1。意味着，键值对对象都会存储到数组索引 1位置，这样就形成一个非常长的链表。相当于每存储一个对象都会发生“hash冲突”，HashMap 也退化成了一个“链表”。
ii. 一种简单和常用的算法是（相除取余算法）：
hash 值 = hashcode%数组长度
这种算法可以让 hash 值均匀的分布在[0,数组长度-1]的区间。但是，这种算法由于使用了“除法”，效率低下。JDK 后来改进了算法。首先约定数组长度必须为 2 的整数幂，这样采用位运算即可实现取余的效果：hash 值 =hashcode&(数组长度-1)。
/**
* Computes key.hashCode() and spreads (XORs) higher bits of hash
* to lower. Because the table uses power-of-two masking, sets of
* hashes that vary only in bits above the current mask will
* always collide. (Among known examples are sets of Float keys
* holding consecutive whole numbers in small tables.) So we
* apply a transform that spreads the impact of higher bits
* downward. There is a tradeoff between speed, utility, and
* quality of bit-spreading. Because many common sets of hashes
* are already reasonably distributed (so don't benefit from
* spreading), and because we use trees to handle large sets of
* collisions in bins, we just XOR some shifted bits in the
* cheapest possible way to reduce systematic lossage, as well as
* to incorporate impact of the highest bits that would otherwise
* never be used in index calculations because of table bounds.
*/
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}/**
* Associates the specified value with the specified key in this map.
* If the map previously contained a mapping for the key, the old
* value is replaced.
*
* @param key key with which the specified value is to be associated
* @param value value to be associated with the specified key
* @return the previous value associated with {@code key}, or
* {@code null} if there was no mapping for {@code key}.
* (A {@code null} return can also indicate that the map
* previously associated {@code null} with {@code key}.)
*/
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
/**
* Implements Map.put and related methods.
*
* @param hash hash for key
* @param key the key
* @param value the value to put
* @param onlyIfAbsent if true, don't change existing value
* @param evict if false, the table is in creation mode.
* @return previous value, or null if none
*/
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)
n = (tab = resize()).length;
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
else if (p instanceof TreeNode)
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
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);
return oldValue;
}
}
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}添加元素：
/**
* Associates the specified value with the specified key in this map.
* If the map previously contained a mapping for the key, the old
* value is replaced.
*
* @param key key with which the specified value is to be associated
* @param value value to be associated with the specified key
* @return the previous value associated with {@code key}, or
* {@code null} if there was no mapping for {@code key}.
* (A {@code null} return can also indicate that the map
* previously associated {@code null} with {@code key}.)
*/
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
} /**
* Implements Map.put and related methods.
*
* @param hash hash for key
* @param key the key
* @param value the value to put
* @param onlyIfAbsent if true, don't change existing value
* @param evict if false, the table is in creation mode.
* @return previous value, or null if none
*/
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)
n = (tab = resize()).length;
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
else if (p instanceof TreeNode)
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
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);
return oldValue;
}
}
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}数组扩容：
/**
* Initializes or doubles table size. If null, allocates in
* accord with initial capacity target held in field threshold.
* Otherwise, because we are using power-of-two expansion, the
* elements from each bin must either stay at same index, or move
* with a power of two offset in the new table.
*
* @return the table
*/
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
if (oldCap > 0) {
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // preserve order
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}3. TreeMap 容器类
TreeMap 和 HashMap 同样实现了 Map 接口，所以，对于 API 的用法来说是没有区别的。HashMap 效率高于 TreeMap；TreeMap 是可以对键进行排序的一种容器，在需要对键排序时可选用 TreeMap。TreeMap 底层是基于红黑树实现的。
在使用 TreeMap 时需要给定排序规则：1.元素自身实现比较规则；2.通过比较器实现比较规则
元素自身实现比较规则：
package cn.pxy.test;
public class Users implements Comparable<Users>{
private String username;
private int userage;
public Users(String username,int userage) {
this.username=username;
this.userage=userage;
}
public Users() {
}
@Override
public boolean equals(Object o) {
System.out.println("equals...");
if(this==o) {
return true;
}
if(o==null||getClass()!=o.getClass()) {
return false;
}
Users users=(Users) o;
if(userage!=users.userage) {
return false;
}
return username!=null?username.equals(users.username):users.username==null;
}
@Override
public int hashCode() {
int result=username!=null?username.hashCode():0;
result=31*result+userage;
return result;
}
public String getUsername() {
return username;
}
public void setUsername(String username) {
this.username = username;
}
public int getUserage() {
return userage;
}
public void setUserage(int userage) {
this.userage = userage;
}
@Override
public String toString() {
return "Users{"+"username='"+username+'\''+",userage="+userage+'}';
}
//定义比较规则
//正数：大；负数：小；0：相等
@Override
public int compareTo(Users o) {
if(this.userage>o.getUserage()) {
return 1;
}
if(this.userage==o.getUserage()) {
return this.username.compareTo(o.getUsername());
}
return -1;
}
}package cn.pxy.test;
import java.util.Map;
import java.util.Set;
import java.util.TreeMap;
public class TreeMapTest {
public static void main(String[] args) {
Map<Users,String> map=new TreeMap<>();
Users u1=new Users("pxy",18);
Users u2=new Users("dhy",22);
Users u3=new Users("pxyxs",19);
map.put(u1, "pxy");
map.put(u2,"dhy");
map.put(u3, "pxyxs");
Set<Users> keys=map.keySet();
for(Users key:keys) {
System.out.println(key+"******"+map.get(key));
}
}
}运行结果：
通过比较器实现比较规则：
package cn.pxy.test;
public class Student {
private String name;
private int age;
public Student(String name,int age) {
this.name=name;
this.age=age;
}
public Student() {
}
@Override
public String toString() {
return "Student {" + "name='" + name + '\'' + ", 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;
}
@Override
public boolean equals(Object obj) {
if(this==obj) {
return true;
}
if(obj==null||getClass()!=obj.getClass()) {
return false;
}
Student student=(Student) obj;
if(age!=student.age) {
return false;
}
return name!=null?name.equals(student.name):student.name==null;
}
@Override
public int hashCode() {
int result=name!=null?name.hashCode():0;
result=31*result+age;
return result;
}
}package cn.pxy.test;
import java.util.Comparator;
//定义比较规则
public class StudentComparator implements Comparator<Student>{
public int compare(Student o1,Student o2) {
if(o1.getAge()>o2.getAge()) {
return 1;
}
if(o1.getAge()==o2.getAge()) {
return o1.getName().compareTo(o2.getName());
}
return -1;
}
}package cn.pxy.test;
import java.util.Map;
import java.util.Set;
import java.util.TreeMap;
public class TreeMapTest {
public static void main(String[] args) {
Map<Student,String> treeMap=new TreeMap<>(new StudentComparator());
Student u1=new Student("pxy",18);
Student u2=new Student("dhy",22);
Student u3=new Student("pxyxs",19);
treeMap.put(u1, "pxy");
treeMap.put(u2,"dhy");
treeMap.put(u3, "pxyxs");
Set<Student> keys=treeMap.keySet();
for(Student key:keys) {
System.out.println(key+"******"+treeMap.get(key));
}
}
}运行结果：
4. Iterator 迭代器
4.1 Iterator 迭代器接口介绍
Collection接口继承了Iterable接口，在该接口中包含一个名为iterator的抽象方法，所有实现了Collection接口的容器类对该方法做了具体实现。iterator方法会返回一个Iterator接口类型的迭代器对象，在该对象中包含了三个方法用于实现对单例容器的迭代处理。
Iterator对象的工作原理：
Iterator接口定义了如下方法：
1.boolean hasNext(); //判断游标当前位置是否有元素，如果有返回true，否则返回false；
2.Object next();//获取当前游标所在位置的元素，并将游标移动到下一个位置；
3.void remove();//删除游标当前位置的元素，在执行完next后该操作只能执行一次；
4.2 迭代器的使用
使用 Iterator 迭代 List 接口类型容器：
package cn.pxy.test;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
public class IteratorListTest {
public static void main(String[] args) {
//实例化容器
List<String> list = new ArrayList<>();
list.add("a");
list.add("b");
list.add("c");
//获取元素
//获取迭代器对象
Iterator<String> iterator = list.iterator();
//方式一:在迭代器中，通过 while 循环获取元素
while(iterator.hasNext()){
String value = iterator.next();
System.out.println(value);
}
System.out.println("-------------------------------");
//方法二：在迭代器中，通过 for 循环获取元素
for(Iterator<String> it = list.iterator();it.hasNext();){
String value = it.next();
System.out.println(value);
}
}
}运行效果：
使用 Iterator 迭代 Set 接口类型容器：
package cn.pxy.test;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Set;
public class IteratorSetTest {
public static void main(String[] args) {
//实例化 Set 类型的容器
Set<String> set = new HashSet<>();
set.add("a");
set.add("b");
set.add("c");
//方式一：通过 while 循环
//获取迭代器对象
Iterator<String> iterator = set.iterator();
while(iterator.hasNext()){
String value = iterator.next();
System.out.println(value);
}
System.out.println("-------------------------");
//方式二：通过 for 循环
for(Iterator<String> it = set.iterator();it.hasNext();){
String value = it.next();
System.out.println(value);
}
}
}运行结果：
在迭代器中删除元素：
package cn.pxy.test;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
public class IteratorRemoveTest {
public static void main(String[] args) {
List<String> list = new ArrayList<>();
list.add("a");
list.add("b");
list.add("c");
list.add("d");
Iterator<String> iterator = list.iterator();
while(iterator.hasNext()){
//不要在一次循环中多次调用 next 方法。
String value = iterator.next();
if("c".equals(value)){
iterator.remove();
}
}System.out.println("----------------");
for(Iterator<String> it = list.iterator();it.hasNext();){
System.out.println(it.next());
list.add("dddd");
}
}
}5. Collections 工具类
Collections 是一个工具类，它提供了对 Set、List、Map 进行排序、填充、查找元素的辅助方法。该类中所有的方法都为静态方法。
常用方法：
- void sort(List) //对 List 容器内的元素排序，排序的规则是按照升序进行排序。
- void shuffle(List) //对 List 容器内的元素进行随机排列。
- void reverse(List) //对 List 容器内的元素进行逆续排列 。
- void fill(List, Object) //用一个特定的对象重写整个 List 容器。
- int binarySearch(List, Object)//对于顺序的 List 容器，采用折半查找的方法查找特定对象
5.1 对 List 类型容器进行排序处理：
package cn.pxy.test;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
public class CollectionsSortTest {
public static void main(String[] args) {
List<String> list = new ArrayList<>();
list.add("c");
list.add("b");
list.add("d");
list.add("a");
//通过 Collections 工具类中的 sort 方法完成排序
Collections.sort(list);
for(String str:list){
System.out.println(str);
}
}
}运行结果：
5.2 对 List 类型容器进行随机排序：
package cn.pxy.test;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
public class CollectionsSortTest {
public static void main(String[] args) {
List<String> list = new ArrayList<>();
list.add("c");
list.add("b");
list.add("d");
list.add("a");
//通过 Collections 工具类中的 sort 方法完成排序
Collections.sort(list);
for(String str:list){
System.out.println(str);
}
System.out.println("*******");
List<String> list2 = new ArrayList<>();
list2.add("a");
list2.add("b");
list2.add("c");
list2.add("d");
//洗牌处理
Collections.shuffle(list2);
for(String str:list2){
System.out.println(str);
}
}
}运行结果：
免责声明：本站所有文章内容,图片，视频等均是来源于用户投稿和互联网及文摘转载整编而成，不代表本站观点，不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益，请在线联系站长,一经查实,本站将立刻删除。 本文来自网络,若有侵权，请联系删除，如若转载，请注明出处：https://itzsg.com/48513.html
