流年似水博客开通了,本站主要是写关于Web和大数据方面内容,正在更新中,欢迎大家光临!
  1. 文章:97 篇
  2. 总浏览:35,095 次
  3. 评论:22条
  4. 最后更新:2020-06-08
  5. 分类目录:39 个

Java之集合(Map体系)

Java l, xy 749℃ 0评论

  1.   Map集合

(1)      特点

1           保存一组键值对

2           键不能重复,值可以重复。即一个键只能对应一个值,多个值可以对应一个键

(2)      常见方法(使用default修饰的方法为JDK8新增的默认方法

1           新增

1)         V put(K key,V value)

2)         void putAll(Map<? extends K,? extends V> m)

2           修改

1)         V put(K key,V value)

2)         default void replaceAll(BiFunction<? extends K,? extends V> function):遍历对map中的每一个键值应用function,最后function的返回值为最后的值得修改结果。如果在遍历过程中发生删除操作,则抛出ConcurrentModificationException

3)         default V putIfAbsent(K key,V value) :get(key)返回null时,将key键对应的值修改为value

4)         default boolean replace(K key,V oldValue,V newValue) :map中包含指定的key-oldValue键值对,并且value的值不为null,则根据key将其替换,并返回true,否则返回false

5)         default V replace(K key,V value): 如果map中包括key,则将使用value替换原来的值,并返回value;如果不包含key,则直接返回null

6)         default V computeIfAbsent(K key,Function<? super K , ? extends V > mappingFunction) :如果map中包含keykey对应的值不为null,则返回key对应的值;如果mapkey对应的值为null或者不存在key,则将key对应的值修改为应用mappingFunction以后的返回结果。

7)         default V computeIfPresent(K key,BiFunction<? super K,? extends V,? extends V > remappingFunction) :如果map中包含key,并且key对应的值不为null时,将对key和值应用remappingFunction方法,如果返回不为null,则修改key的值为返回值并返回,如果为null,则删除key,返回null。如果不包含key则直接返回null

8)         default V compute(K key,BiFunction<? super K, ? extends V,? extends V > remappingFunction):对传入的key,以及改key对应的值应用remappingFunction方法,如果返回结果不为null,直接修改该key对应的值为返回结果;如果返回结果为null,原map中包含key,并且key对应的值不为null,则直接删除并返回null,否则不做任何操作

9)         default V merge(K key,V value,BiFunction<? super K,? super V,? extends V > remappingFunction) :如果原key对应的值为null,则修改key的值为value;如果原key对应的value不为null,则对老值和value应用remappingFunction方法,如果返回结果为null,则删除key,否则修改key为返回的值

3           删除

1)         V remove(Object key)

2)         void clear()

3)         default boolean remove(Object key,Object value) :map中包含指定的key-value键值对,并且value的值不为null,则根据key将其删除,并返回true,否则返回false

4)          

4           判断

1)         boolean isEmpty()

2)         boolean containsKey(Object key)

3)         boolean containsValue(Object value)

4)         boolean equals(Object o) : 比较mapentrySet()方法内保存的元素是否全部相等

5           获取

1)         int size()

2)         V get(Object key)

3)         Collection<V> values():获取Map中值得集合,注意:map任何对值得操作都会影响到返回的Collection集合,反之亦然。

4)         default V getOrDefault(Object key,V default):根据key获取值,如果key对应的valuenull或者不包含key,则返回传入的默认值,否则返回key对应的值

6           遍历

1)         Set<K> keySet() 获取Map中键的集合,注意:Map任何对键的操作都会影响到返回的Set集合,反之亦然。

Map<String, Integer> maps = new HashMap<>();
maps.put("aa", 11);
maps.put("bb", 22);
Set<String> keySet = maps.keySet();
for (String key : keySet) {
    //打印:aa    bb
    System.out.print(key + "\t");
}
//新增元素
maps.put("cc", 33);
for (String key : keySet) {
    //打印:aa    bb    cc
    System.out.print(key + "\t");
}

2)         Set<Map.Entry<K,V>> entrySet():获取Map中键值对关系的集合,注意:map任何对键或者的操作都会影响到返回的Set集合,反之亦然

/**
* 遍历方式二: entrySet
*/
@Test
public void test3() {
    for (Map.Entry<Book, Double> entry : map.entrySet()) {
        System.out.println("key = " + entry.getKey() + "... value = " + entry.getValue());
    }
}

3)         default void foreach(BiConsume<? super K> , ? super V> action) :map集合中的所有元素应用action。注意:如果在遍历的过程中删除元素,则会抛出ConcurrentModificationException

(3)      遍历方式

1)         Set<K> keySet() 获取Map中键的集合,注意:Map任何对键的操作都会影响到返回的Set集合,反之亦然。

Map<String, Integer> maps = new HashMap<>();
maps.put("aa", 11);
maps.put("bb", 22);
Set<String> keySet = maps.keySet();
for (String key : keySet) {
    //打印:aa    bb
    System.out.print(key + "\t");
}
//新增元素
maps.put("cc", 33);
for (String key : keySet) {
    //打印:aa    bb    cc
    System.out.print(key + "\t");
}

2)         Set<Map.Entry<K,V>> entrySet():获取Map中键值对关系的集合,注意:map任何对键或者的操作都会影响到返回的Set集合,反之亦然

/**
* 遍历方式二: entrySet
*/
@Test
public void test3() {
    for (Map.Entry<Book, Double> entry : map.entrySet()) {
        System.out.println("key = " + entry.getKey() + "... value = " + entry.getValue());
    }
}

(4)      常见的实现类

1           HashMap

1)         底层结构

 

数据结构

底层维护数组

初始化时机(这里指调用无参构造方法创建对象时)

JDK7

哈希表+单向链表

Entry<K,V> table

创建对象时

JDK8

哈希表+单向链表+红黑树

Node<K,V> table

第一次添加元素时

 

2)         特点

  1. 基于哈希表实现
  2. JDK1.2版本推出
  3. 允许nullnull
  4. 不保证有序

3)         常用方法:

  1. 常用方法同Map接口
  2. 构造器:

a)         public HashMap()

b)        public HashMap(int initialCapacity)

c)         public HashMap(int initialCapacity,float loadFactor)

d)        public HashMap(Map<? extends K,? extends V > m)

 

4)         源码分析

  1. 维护成员变量

a)         扩容临界值(int threshold

/**
* The next size value at which to resize (capacity * load factor).
*
* @serial
*/
// (The javadoc description is true upon serialization.
// Additionally, if the table array has not been allocated, this
// field holds the initial array capacity, or zero signifying
// DEFAULT_INITIAL_CAPACITY.)
int threshold;

b)        加载因子(final float loadFactor

/**
* The load factor for the hash table.
*
* @serial
*/
final float loadFactor;

c)         默认初始化容量(容量必须是2的幂)(final int DEFAULT_INITIAL_CAPACITY)

/**
* The default initial capacity - MUST be a power of two.
*/
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

d)        map集合最大的容量(final int MAXNIUM_CAPACITY)

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

e)         默认的加载因子(final float DEFAULT_LOAD_FACTOR )

/**
* The load factor used when none specified in constructor.
*/
static final float DEFAULT_LOAD_FACTOR = 0.75f;

f)          链表结构变成树结构的最小节点数(final int TREEIFY_THRESHOLD)

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

g)         重新resize以后,是否untreefy的临界值,当小于等于该值得时候将树转换为链表(未验证)(final int UNTREEITY_THRESHOLD)

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

h)        链表转换为树时的最小map的容量(final int MIN_TREEIFY_CAPATICY)

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

i)           保存哈希表的节点数组(Node<K,V> table

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

j)          保存map集合中保存键值对的个数(int size

/**
* The number of key-value mappings contained in this map.
*/
transient int size;

k)         保存map集合内部结构被修改的次数(int modCount

/**
* The number of times this HashMap has been structurally modified
* Structural modifications are those that change the number of mappings in
* the HashMap or otherwise modify its internal structure (e.g.,
* rehash).  This field is used to make iterators on Collection-views of
* the HashMap fail-fast.  (See ConcurrentModificationException).
*/
transient int modCount;

l)           保存map集合键值对的集合(Set <Map.Entry<K,V>>entrySet

/**
* Holds cached entrySet(). Note that AbstractMap fields are used
* for keySet() and values().
*/
transient Set<Map.Entry<K,V>> entrySet;

m)      保存key的集合和保存value集合的变量(在AbstractMap中)

/**
* Each of these fields are initialized to contain an instance of the
* appropriate view the first time this view is requested.  The views are
* stateless, so there's no reason to create more than one of each.
*/
transient volatile Set<K>        keySet;
transient volatile Collection<V> values;

5)         扩容机制

  1. 若使用无参构造器创建对象,则在第一个添加的时候会初始化capacity16(默认DEFAULT_INITIAL_CAPACITY),loadFactor0.75(默认DEFAULT_LOAD_FACTOR
  2. 若使用指定容量的构造器创建对象,则在第一个添加的时候会初始化capacity为指定容量是大于该数的最接近2n次幂的值。

/**
* Returns a power of two size for the given target capacity.
*/
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;
}

  1. 其他一律扩容为原容量的2倍,扩容临界值也扩容为原来的2

/**
* 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) {
/**
tab: 保存内部维护的原table数组
p:保存根据添加元素需要保存table数组中下标的位置所保存的值
n:保存table的元长度
i:保存根据添加元素需要保存table数组中下标的位置

**/
Node<K,V>[] tab; Node<K,V> p; int n, i;
//无参构成器创建对象
if ((tab = table) == null || (n = tab.length) == 0)
//初始化table数组长度为16,以及threshold的值为12
n = (tab = resize()).length;
//计算保存元素下标的位置,如果该位置没有保存其他元素,则直接保存
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
/**
e:保存将要保存的新值
k: 保存以前元素的k
**/
Node<K,V> e; K k;
//判断添加元素的hash值是否和要保存下标位置上的值得hash相等 && (key == 原来的key || (key != null && key.equals(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);
//判断如果链表元素个数为8,则尝试将链表转换为树
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;
}
}
// 当key的hash相同,equals方法也返回true是,替换原来的值
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;

6)         去重机制

  1. 元素的hashCode方法equals方法
  2. 去重顺序

a)         首先根据元素的hashCode计算出一个新的hash

b)        根据计算出的hash,计算出要到保存table数组中的位置

c)         如果位置上有元素,则会先比较hash是否相等,如果相等,则会比较key是否相等(使用==  equals 比较),不等则保存;相等则使用新的value值覆盖原来的valuy值。

p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k)))

7)         链表转换为树的条件

  1. 链表上有大于等于8个元素并且table数组的长度大于等于64
  2. 如果满足链表上的元素大于等于8,但是table数组的长度不大于等于64的话,则会选择扩容来重新排序链表


/**
* 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;
//将链表上的元素分为两组 low 和 hight组,
//分配标准: 当前元素的hash & 原table数组长度 是否等于0
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;
//将低组保存到新table数组的与元素table数组相同的位置
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
//将高组保存到新table数组的(原位置 + 原数组长度 )位置上
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}


2           TreeMap

1)         底层结构

  1. 红黑树

2)         特点:

  1. 能够自动排序(默认按照自然排序),也可以传入一个比较器,实现定制排序
  2. 线程不安全的

3)         常用方法:

  1. 构造方法:

a)         public TreeMap()

b)        public TreeMap(Comparator<? super K> comparator)

c)         public TreeMap(Map<? extends K, ? extends V> m)

d)        public TreeMap(SortedMap<K, ? extends V> m) SortedMap内保存的内容添加到TreeMap,并且保持和SortedMap相同的排序规则             

  1. 删除

a)         Map.Entry<K,V> pollFirstEntry() 删除第一个entry

b)        Map.Entry<K,V> pollLastEntry() 删除最后一个entry

  1. 获取

a)         Comparator<? super K> comparator() :获取比较器

b)        K firstKey()

c)         K lastKey()

d)        Map.Entry<K,V> firstEntry()

e)         Map.Entry<K,V> lastEntry()

f)          Map.Entry<K,V> lowerEntry(K key) 获取比指定keymap中可以不包含)小的第一个key的键值对映射,如果没有,则返回null

g)         K lowerKey(K key):返回比指定key小的里面最大的key(不包含key本身),如果没有,则返回null

h)        Map.Entry<K,V> floorEntry(K key) :返回小于或者等于指定keykey-value对,如果没有返回null

i)           K floorKey(K key):返回小于或者等于指定keykey,如果没有则返回null

j)          Map.Entry<K,V> ceilingEntry(K key):返回大于或者等于keykey-value值,没有返回null

k)         K ceilingKey(K key): 返回大于或者等于keykey,如果没有返回null

l)           Map.Entry<K,V> highterEntry(K key) :返回大于keykey-value值,如果没有返回null

m)      K highterEntry(K key) :返回大于keykey,如果没有返回null

n)        NavigableMap<K,V> descendingMap() : 返回一个倒序的map

o)        NavigableSet<K> navigableKeySet() : 返回key的集合

p)        NavigableSet<K> descendingKeySet() : 返回倒序的key的集合

q)        NabigableMap<K,V> subMap(K fromKey,boolean fromInclusive,K toKey,boolean toInclusive) : 获取子map

r)          SortMap<K,V> subMap(K fromKey,K toKey):包含fromKey,不包含toKey

s)         NavigableMap<K,V> headMap(K key,boolean inclusive) : 从头开始获取小于或者等于指定keymap集合,true--包含;false--不包含

t)          SortMap<K,V>  headMap(K toKey) : 从开始到tokey,不包含toKey

u)        NavigableMap<K,V> tailMap(String key,boolean inclusive) : key到结尾获取大于或者等于keymap集合。true -- 包含 false - 不包含

v)         SortMap<K,V> tailMap(K fromKey) : fromKey到结尾,包含fromKey

 

4)         遍历方式

  1. Map
  2. 多了倒序遍历

5)         去重原则

  1. 自然排序

a)         Comparable接口的compareTo()方法返回0,表示元素重复(相等)

  1. 定制排序

a)         Comparator接口的compare()方法返回0,表示元素重复(相等)

3           HashTable

1)         特点:

  1. 线程安全的
  2. 不允许nullnull
  3. 版本1.0

2)         特有方法:

3)         遍历方式

4)         使用:

  1. 不经常使用

 

4           LinkedHashMap

1)         数据结构:

  1. 链表 + (哈希表 + 链表 + 数组)

2)         特点:

  1. 技能保证元素的有序性
  2. 又能拥有HashMap的特点

3)         常用方法:

5           Properties

1)         特点:

  1. Hashtable的子类
  2. 线程安全的
  3. 不能保存nullnull
  4. 一般只用来保存字符串(keyvalue都是字符串)

2)         应用:

  1. 一般应用于保存简单的配置信息,例如数据库配置

 

3)         常用方法

  1. 构造:

a)         public Properties()

b)        public Properties(Properties pro)

  1. 说明:具备Hashtable的所有方法
  2. 新增:

a)         Object setProperty(String key,String value)

  1. 修改

a)         Object setProperty(String key,String value)

  1. 读取配置

a)         synchronized void load(InputStream inStream)

b)        synchronized void load(Reader reader)

c)         synchronized void loadFromXML(InputStram in)


@Test
public void test2() throws IOException {
Properties properties = new Properties();
properties.loadFromXML(new FileInputStream("test.xml"));
properties.list(System.out);

}
打印结果:
-- listing properties --
aa=123
bb=456
cc=789
  1. 获取

a)         String getProperty(String key)

b)        String getProperty(String key,String defaultValue)

c)         Enumeration<?> propertyNames() : 返回所有的key枚举类

d)        Set<String>  StringPropertyNames() 返回key的集合,String类型

  1. 保存到文件

a)         void store(OutputStream out,String comments)

b)        void store(Writer writer , String comments)

c)         void storeToXML(OutputStream os,String comment,String encoding)

d)        void storeToXML(OuputStream os,String comment):默认使用UTF-8编码

@Test
public void test1() throws IOException {
Properties properties = new Properties();
properties.setProperty("aa","123");
properties.setProperty("bb","456");
properties.setProperty("cc","789");

properties.storeToXML(new FileOutputStream("test.xml"),"这是注释");
}

4)         遍历方式

  1. Hashtalbe的遍历方式
  2. void list(PrintStream out)
  3. void list(PrintWrite out)

 

转载请注明:流年似水 » Java之集合(Map体系)

喜欢 (0)or分享 (0)

Warning: copy(https://cn.gravatar.com/avatar/?s=54&d=%2Fwp-content%2Fthemes%2Fyusi1.0%2Fimg%2Fdefault.png&r=g): failed to open stream: HTTP request failed! HTTP/1.1 400 Bad Request in /usr/share/nginx/html/timewentby/wp-content/themes/yusi1.0/functions.php on line 239

Warning: copy(/wp-content/themes/yusi1.0/img/default.png): failed to open stream: No such file or directory in /usr/share/nginx/html/timewentby/wp-content/themes/yusi1.0/functions.php on line 243
发表我的评论
取消评论

表情

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址