Java Map接口常用实现类

/ 默认分类default / 0 条评论 / 3450浏览

java学习

public interface Map<K,V> {
// Query Operations

// Map中的键值对数量
int size();

// Map是否为空，即没有键值对
boolean isEmpty();

// Map中是否包含特定的键
boolean containsKey(Object key);

// Map中是否包含特定的值
boolean containsValue(Object value);

// 根据key获取对应的value，如果key不存在则返回null
V get(Object key);

// Modification Operations

// 向Map中放入一个键值对，返回键值对的值
// 如果键在Map中已存在，则使用给定的值来更新原来的键值对的值，返回原来的旧值
V put(K key, V value);

// 根据key移除键值对，如果key在Map中不存在，则返回null，否则返回key对应的value
V remove(Object key);

// Bulk Operations

// 把另一个Map的键值对放入该Map，向当于将另一个Map的键值对调用put方法放到该Map中
void putAll(Map<? extends K, ? extends V> m);

// 移除Map中所有的键值对
void clear();

// Views

// 返回该Map中所有键的集合，返回类型为Set，因为键都是不相同的
Set<K> keySet();

// 返回该Map中的所有值的集合，返回类型为Colleectino
Collection<V> values();

// 返回该Map中所有键值对的集合，返回类型为Set<Map.Entry<K, V>>
// Map.Entry表示一个键值对
Set<Map.Entry<K, V>> entrySet();

// 表示一个键值对
interface Entry<K,V> {
    // 返回该键值对的key
    K getKey();

    // 返回该键值对的value
    V getValue();

    // 修改该键值对的value
    V setValue(V value);

    // 判断该键值对与指定的键值对是否相等
    boolean equals(Object o);

    int hashCode();

    // 省略了部分方法
}

// Comparison and hashing

boolean equals(Object o);

int hashCode();

}

非线程的实现类 HashMap HashMap是Map接口的一种哈希表实现，它可以存放null（key和value都可以为null），它的get和put等操作时间复杂度均为0(1)

构造器 默认值 默认值比较多，而且作用比较大，最主要的是阈值（threshold，根据容量和负载因此进行计算）和负载因子（loadFactor，默认为0.75），默认的容量为16。扩容的时候新容量变成旧容量×2（newCap = oldCap << 1）

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

/**

线程安全的实现类 Hashtable

HashTable不允许存放null（key和value都不能为null，因为它的hash算法会调用key的hashCode方法，并且检测到value为null会抛出异常），添加和获取等操作的时间复杂度和HashMap一致（哈希冲突严重的时候性能会比HashMap差很多）
public Hashtable(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
    throw new IllegalArgumentException("Illegal Capacity: "+
                                       initialCapacity);
if (loadFactor <= 0 || Float.isNaN(loadFactor))
    throw new IllegalArgumentException("Illegal Load: "+loadFactor);

if (initialCapacity==0)
    initialCapacity = 1;
this.loadFactor = loadFactor;
table = new Entry<?,?>[initialCapacity];
threshold = (int)Math.min(initialCapacity * loadFactor, MAX_ARRAY_SIZE + 1);

}

public Hashtable(int initialCapacity) { this(initialCapacity, 0.75f); }

public Hashtable() { this(11, 0.75f); }

public Hashtable(Map<? extends K, ? extends V> t) { this(Math.max(2*t.size(), 11), 0.75f); putAll(t); }

本站文章除注明转载/出处外，均为本站原创或翻译，转载前请务必署名,转载请标明出处
最后编辑时间为: 2019/10/23 23:53