侧边栏壁纸
博主头像
王小木人

这是很长,很好的一生

  • 累计撰写 141 篇文章
  • 累计创建 43 个标签
  • 累计收到 7 条评论

目 录CONTENT

文章目录

Map集合接口

王小木人
2021-05-24 / 0 评论 / 0 点赞 / 949 阅读 / 5,221 字

collection集合保存数据主要为了输出,map集合保存数据是为了查找,保存二元偶对象 Map<key,value>。

数据按(key=value)方式存储,在of方法存储时key不能重复不能为null。

常用子类:HashMap,Hashtable,TreeMap,LinkedHashMap.

HashMap:

public class HashMap<K,V>
extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable

无序存储,

同样的key保存时,可以重复的key,但是新的key值会覆盖原来的key,key可为null,使用put方法保存数据时,put方法会返回旧数据的value,没有旧的key返回null, 

无参构造:

public HashMap() {
        this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
    }

static final float DEFAULT_LOAD_FACTOR = 0.75f;

Hasp中put方法

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) {
        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;
    }

在使用put()方法进行数据保存时会调用putVal()方法,同时会将key进行hash处理(生成一个hash码),而对于putVal()方法里面依然会提供有一个Node节点类进行数据的保存,在使用putval方法过程中会调用resize()进行容量的扩充。

那么怎么进行hashmap的put时容量扩充呢?

在HashMap类里面提供有一个“DEFAULT_INITIAL_CAPACITY”( static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16)常量,作为初始化容量配置大小为16,也就是16个元素。

当保存的内容容量超过阈值,static final float DEFAULT_LOAD_FACTOR = 0.75f;,16*0.75=12,保存12个元素时便会进行容量的扩充,调用resize()扩充。

在进行容量扩充时采用成倍的扩充模式,每次都扩充2倍的容量。

HashMap的工作原理:

在HashMap之中进行数据存储的依然是利用了Node类完成的,使用链表和二叉树进行Node存储。

链表(时间复杂度o(n)),二叉树(O(logn));

jdk1.8出现改变,适应大数据,

    HashMap提供static final int TREEIFY_THRESHOLD = 8;阈值常量,当低于等于8时采用链表存储,大于8时则会转化为后红黑树以实现树的平衡,并且利用左旋与右旋保证数据查询的性能。

LinkedHashMap:

Module java.base

Package java.util

Class LinkedHashMap<K,V>
java.lang.Object
java.util.AbstractMap<K,V>
java.util.HashMap<K,V>
java.util.LinkedHashMap<K,V>
Type Parameters:

K - the type of keys maintained by this map

V - the type of mapped values

All Implemented Interfaces:

Serializable, Cloneable, Map<K,V>

链表保存,保存的数量不能太大,无法转换为红黑树,当大小不会轻易改变时适合采用LinkedHashMap存储顺序为添加数据时的顺序,   同样的key保存时,可以重复的key,但是新的key值会覆盖原来的key,key可为null,使用put方法保存数据时,put方法会返回旧数据的value,没有旧的key返回null, 

Hashtable:

Module java.base

Package java.util

Class Hashtable<K,V>
java.lang.Object
java.util.Dictionary<K,V>
java.util.Hashtable<K,V>
Type Parameters:

K - the type of keys maintained by this map

V - the type of mapped values

All Implemented Interfaces:

Serializable, Cloneable, Map<K,V>

Direct Known Subclasses:

Properties, UIDefaults

public class Hashtable<K,V>
extends Dictionary<K,V>
implements Map<K,V>, Cloneable, Serializable
是kdk1.0提供,是和Vector,Enumeration属于最早一批动态数组实现类,为了保存下实现了map接口

key 和value 均不能为null,否则会出现nullpointerexception异常,

HashMap与Hashtable区别,

HashMap中方法属于异步操作,非线程安全,允许保存null数据,

Hashtable 中的方法属于同步方法,线程安全的,不允许保存null数据,否则会出现nullpointexception

Map.Entry

数据保存时,元素数据保存在Node节点中,HashMap中Node类实现了Map.Entry接口

所有的key和value 的数据都封装在Map.Entry接口之中,

Module java.base

Package java.util

Interface Map.Entry<K,V>
All Known Implementing Classes:

AbstractMap.SimpleEntry, AbstractMap.SimpleImmutableEntry

Enclosing interface:

Map<K,V>

public static interface Map.Entry<K,V>
K getKey()
Returns the key corresponding to this entry.

V getValue()
Returns the value corresponding to this entry.

jdk 1.9 之后可以实例化Map.Entry<k,v>

treemap

TreeMap 是一个有序的key-value集合,它是通过红黑树实现的。
TreeMap 继承于AbstractMap,所以它是一个Map,即一个key-value集合。
TreeMap 实现了NavigableMap接口,意味着它支持一系列的导航方法。比如返回有序的key集合。
TreeMap 实现了Cloneable接口,意味着它能被克隆。
TreeMap 实现了java.io.Serializable接口,意味着它支持序列化。

TreeMap基于红黑树(Red-Black tree)实现。该映射根据其键的自然顺序进行排序,或者根据创建映射时提供的 Comparator 进行排序,具体取决于使用的构造方法。
TreeMap的基本操作 containsKey、get、put 和 remove 的时间复杂度是 log(n) 。
另外,TreeMap是非同步的。 它的iterator 方法返回的迭代器是fail-fastl的。

java.lang.Object
java.util.AbstractMap<K,V>
java.util.TreeMap<K,V>
Type Parameters:

K - the type of keys maintained by this map

V - the type of mapped values

All Implemented Interfaces:

Serializable, Cloneable, Map<K,V>, NavigableMap<K,V>, SortedMap<K,V>

public class TreeMap<K,V>
extends AbstractMap<K,V>
implements NavigableMap<K,V>, Cloneable, Serializable

0

评论区