Java：浅谈 Map

Map 翻译成中文是 映射。

大意是：设有集合a｛a1，a2,a3,┅｝，与集合b{b1,b2,b3,┅},都满足变换群的条件，且集合a与b对应元素之间，能确定一个一一对应的关系（映射法则），使得a1对应b1 。（高中函数定义）设a,b是两个非空的数集，如果按某个确定的对应关系f,使对于集合a中的任意一个数x，在集合b中都有唯一确定的数f(x)和它对应迷你地图java，那么就称f:a--b为集合a到集合b的一个函数，记作y=f(x),x属于集合a。1.先讲清对应法则：然后，根据法则，对于集合a中的每一个元素，在集合b中都有一个(或几个)元素与此相对应。

A 集合中的每一个元素都可以在 B 集合中找到唯一的一个值与之对应。

collection是个java.util下的接口，它是各种集合结构的父接口，继承于它的接口主要有set和list,提供了关于集合的一些操作,如插入、删除、判断一个元素是否其成员、遍历等。map是键值对映射容器，与list和set有明显的区别，而set存储的零散的元素且不允许有重复元素（数学中的集合也是如此），list是线性结构的容器，适用于按数值索引访问元素的情形。大意是：设有集合a｛a1，a2,a3,┅｝，与集合b{b1,b2,b3,┅},都满足变换群的条件，且集合a与b对应元素之间，能确定一个一一对应的关系（映射法则），使得a1对应b1 。

因为 Map 接口并没有继承于 Collection 接口也没有集成 Iterable 接口，所以不能直接对 Map 使用 for-each 操作。

Map 由多个 Entry 组成，把多个 Entry 看成一个集合，即：

Set<Entry> –> Map

Entry：key——value（键值对）

Map就是多个键值对的集合

在 Map 和 Set 中有很多相似的实现类名：

算法

HashSet

HashMap

哈希表

TreeSet

TreeMap

红黑树

LinkedHashSet

LinkedHashMap

哈希表/链表

数据结构就包含了算法，我们应该将数据结构分解为集合与算法——数据结构的本质不是结构，而是集合与算法，这看起来很像面向对象中的对象——状态与方法。excel对象中的集合对象有时包括的子对象是不一定的，例如：range对象，可以表示cell的集合，也可以表示column的集合或row的集合，range.getitem(1)可以返回cell或column或row对象。ｅＣｏｇｎｉｔｉｏｎ软件采用的是分形网格 演化算法（ＦＮＥＡ），该算法从单个像元开始，根据像元异质性最小的原则，对像元或像元集合进行合并，最后合 并成一个个影像对象，即影像分割结果。

因此：在 Map 中，所有的 key 就是一个 Set 集合。

public HashSet(Collection<? extends E> c) {
    map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16));
    addAll(c);
}

set里面不允许有重复的元素，所谓重复，即不能有两个相等（注意，不是仅仅是相同）的对象，即假设set集合中有了一个a对象，现在我要向set集合再存入一个b对象，但b对象与a对象equals相等，则b对象存储不进去，所以，set集合的add方法有一个boolean的返回值，当集合中没有某个元素，此时add方法可成功加入该元素时，则返回true，当集合含有与某个元素equals相等的元素时，此时add方法无法加入该元素迷你地图java，返回结果为false。例如hashmap底层实现，查找key时，先对其进行hash算法得到哈希值，如果hash值相同，再去比较key是否相等，key相等才能说找到了正确的结果。：采用哈希算法来实现set接口唯一性保证：重复对象equals方法返回为true重复对象hashcode方法返回相同的整数不同对象 哈希码 尽量保证不同（提高效率） sortedset。

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

常用红黑树算法，此时 Map 中的 key 会按照自然顺序或定制排序进行排序，key 也不允许重复，key 判断重复的标准是：compareTo/compare 的返回值是否为 0。

public V put(K key, V value) {
    Entry<K,V> t = root;
    if (t == null) {
        compare(key, key); // type (and possibly null) check
        root = new Entry<>(key, value, null);
        size = 1;
        modCount++;
        return null;
    }
    int cmp;
    Entry<K,V> parent;
    // split comparator and comparable paths
    Comparator<? super K> cpr = comparator;
    if (cpr != null) {
        do {
            parent = t;
            cmp = cpr.compare(key, t.key);
            if (cmp < 0)
                t = t.left;
            else if (cmp > 0)
                t = t.right;
            else
                return t.setValue(value);
        } while (t != null);
    }
    else {
        if (key == null)
            throw new NullPointerException();
        @SuppressWarnings("unchecked")
            Comparable<? super K> k = (Comparable<? super K>) key;
        do {
            parent = t;
            cmp = k.compareTo(t.key);
            if (cmp < 0)
                t = t.left;
            else if (cmp > 0)
                t = t.right;
            else
                return t.setValue(value);
        } while (t != null);
    }
    Entry<K,V> e = new Entry<>(key, value, parent);
    if (cmp < 0)
        parent.left = e;
    else
        parent.right = e;
    fixAfterInsertion(e);
    size++;
    modCount++;
    return null;
}

采用链表和哈希表算法，此时 Map 中的 key 类保证先后添加顺序，key 不允许重复，key 判断重复的标准和 HashMap 中的 key 的标准相同。

采用哈希表算法，是 HashMap 的前身（类似于 Vector 是 ArrayList 的前身）：在 Java 的集合框架之前，表示映射关系就使用 Hashtable。所有的方法都使用 synchronized 修饰符，线程安全的，但是性能相对 HashMap 较低。

PS：Hashtable 在 JDK1.0 就出来了，而 Map 类在 JDK1.2 才出来。

Hashtable 的子类，此时要求 key 和 value 都是 String 类型，用来加载资源文件（properties 文件（IO））

public synchronized Object setProperty(String key, String value) {
    return put(key, value);
}

注：一般的，定义 Map 的 key 都使用不可变的类（String）,把 key 作为 value 的唯一名称。

HashMap 和 TreeMap 以及 LinkedHashMap 都是线程不安全的，但是性能较高。

解决方案：Map m = Collection.synchronizedMap（Map 对象）

Hashtable 类实现类线程安全的，但是性能较低。

哈希表算法：做等值查询最快。

树结构算法：做范围查询最快———>应用到索引上。

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/ruanjian/article-106522-1.html