Map

学了Map后，咱们都晓得Map有两种遍历形式，keySet遍历个entrySet遍历， 这里简略介绍一下这两种遍历形式。 首先对于一个Map来说，右key列和value列组成，想遍历这个Map，有两种抉择 第一种keyset的想法是先失去其key列， 应用Map的get(key)办法来获取其对应的值，如下图： 对应的代码是： 第二种思维是这样的，想方法失去Key和Value的映射关系，再从这个关系中失去对应的key和value值，也就是第二种遍历形式，entrySet 如图： 对应的代码是： 以上就是Map的两种遍历形式，心愿对大家有帮忙 这外面顺便介绍下Map.Entry的构造 Map.Entry Entry是一个Map的外部接口，等着Map的子类对象来实现它， 子类对象怎么实现呢？应用外部类的模式，这个外部类通过实现Map.Entry的接口 实现其getKey和getValue办法，实现本人的遍历办法，最初map的子类对象再通过 EntrySet办法将这个外部类对象返回，所有有了

HashMap(jdk8)特点数组+链表+红黑树key非反复双列元素key和value能够为空key只能有一个null非平安结构器无参结构器应用无参结构，第一次put时，会先去校验table表中的长度是否>0，如果小于0，则回去查看初始容量threshold是否大于0，如果没有指定threshold初始容量，则会应用默认的初始容量 16作为table表的长度，默认的加载因子为0.75，只有当汇合put时，才会真正的将table表的长度进行扩容，且下次扩容是达到 初始容量*加载因子=临界值时 会再次触发扩容。 /** * Constructs an empty <tt>HashMap</tt> with the default initial capacity * (16) and the default load factor (0.75). */ public HashMap() { this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted }指定初始化容量和加载因子的结构器应用初始化容量和加载因子的结构器初始容量不得小于0如果初始化容量的大小大于 1 << 30(1的30次方)，会间接应用1的30次方作为初始容量的大小。加载因子不可小于等于0或者不是一个float类型。public HashMap(int initialCapacity, float loadFactor) { if (initialCapacity < 0) throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity); if (initialCapacity > MAXIMUM_CAPACITY) initialCapacity = MAXIMUM_CAPACITY; if (loadFactor <= 0 || Float.isNaN(loadFactor)) throw new IllegalArgumentException("Illegal load factor: " + loadFactor); this.loadFactor = loadFactor; this.threshold = tableSizeFor(initialCapacity); }应用单参初始容量结构器初始容量不可大于1的30次方，且不可小于0默认的加载因子为0.75public HashMap(int initialCapacity) { this(initialCapacity, DEFAULT_LOAD_FACTOR); }应用传入map汇合的结构器public HashMap(Map<? extends K, ? extends V> m) { this.loadFactor = DEFAULT_LOAD_FACTOR; // 计算出容量与加载因子 // 如果容量超过加载因子，则进行扩容。 // 随后遍历Map顺次进行put操作 putMapEntries(m, false); }扩容机制hashMap默认初始化是16个长度，其中默认的加载因子是0.75，当汇合中增加的元素长度达到一个临界值--汇合内元素总数 * 0.75=临界值，即12，当增加完一个元素此时汇合内的长度>12时会进行一个扩容，扩容依照以后容量的两倍进行扩容，并且依据以后的加载因子计算出临界值,当下一次再次触发，则会进行雷同的操作。当咱们在table（即hashmap中的数组）表中，存储元素时，会先去依据key，获取对应的hash值（非hashcode值），是依据按位算法--(h = key.hashCode()) ^ (h >>> 16)--，拿到这个值后，会和表中的长度-1进行按位运算，失去一个索引值，如果表中对应的索引值的元素为为空，则间接将元素增加至数组中的索引，如果存在，则会比拟新元素key的hash值与曾经存在的元素key的hash值是否相等，并且两个元素的key是否相等，如果相等阐明元素反复，则会进行替换操作，如果不相等，则会先去判断，这个索引处的对象类型是不是一颗红黑树，如果是红黑树，则会依照红黑树的形式存储，如果是一条链表，则会顺次比拟链中元素是否相等，如果相等，间接退出，如果不相等，则会在链的最初面减少一个元素，如果创立完后该链的长度>=8，则会判断表table长度是否是64，如果不是64，则会优先扩容table，再往链尾增加新元素的Node节点，如果是64，则会将该链造成红黑树结构。EntitySet对于HashMap汇合的外部类EntitySet解析已知，Map汇合是键值对存储，且经源码剖析，其实，每个k-v元素实质就是一个Node节点对象（HashMap外部类Node<K,V>）,且这个Node对象实现了Map接口的Entity接口，其实当咱们初始化一个Node节点时，newNode(hash, key, value, null)，实际上Map接口的外部类Entity<K,V>保留了Node对象的援用，因为多态的关系，Node对象即是Node类型，又能够向上转型Entity<K,V>,即Entity<K,V>又能够向下转型。为了不便对HashMap汇合的遍历，即会把保留在HashMap中的Node节点的援用保留在EntitySet一份，该汇合寄存的元素类型是Entity，而一个Entity对象就有K-V,EntitySet<Entity<K,V>>，即：Set<Map.Entity<K,V>>,EntitySet中，定义的类型是Map.Entity,然而实际上寄存的还是 HashMap$Node，这是因为Node<K,V> implements Map.Entity<K,V>,当把HashMap$Node 对象寄存到entitySet中后 不便了咱们的遍历和取值。 ...

Golang底层实现系列——map的底层实现本文基于golang 1.14.13map的底层数据结构map的底层实现是一个散列表，map的实现过程实际上就是实现散列表的过程。map次要蕴含两个构造：hmap和bmap。 hmap构造： bmap构造： map的创立map的创立通过生成汇编码能够晓得，调用的时runtime.makemap创立的。 ps:如果你的map初始容量小于等于8会发现走的是runtime.fastrand是因为容量小于8时不须要生成多个桶，一个桶的容量就能够满足（单桶容量通过bucketCnt常量定义）。 这里次要阐明overLoadFactor这个计算B的函数。 func overLoadFactor(count int, B uint8) bool { return count > bucketCnt && uintptr(count) > loadFactorNum*(bucketShift(B)/loadFactorDen)}参数含意： count：以后map容量 B：以后B的值 bucketCnt：单个桶数量（默认为8） loadFactorNum：13 bucketShift : 1<<B loadFactorDen：2 当overLoadFactor返回true时则代表须要扩容,B++。初始时在晓得容量的状况下会间断减少B直到overLoadFactore返回false。 在申请桶空间时用到的函数是makeBucketArry，这个函数会返回指向多个桶空间数组的第一个元素的指针（buckets）和第一个移除桶的指针（nextOverflow）。 <center>桶及溢出桶的散布</center> 如上图（桶及溢出桶的分布图），makeBucketArry实际上就是从内存中申请了一个间断的空间内存，内存大小为bucket.size * buckets总数（根底桶和溢出桶），其中前局部是根底桶（baseBucket）而后是溢出桶。 map的赋值 map的赋值会附带着map的扩容和迁徙，这两局部是map底层实现的要害，会在前面来独自说，除去这两局部的话，map赋值绝对简略，次要是一个hash分为两局部（低位bash和高位hash）低位用于查找bucket，而后tophash疾速判断bucket中各个地位是为空。找到key对应的地位，而后设置key及elem（如果key曾经存在则会间接返回elem的地位，汇编底层会将值赋值到elem对应地位）。 有一点须要特地留神，bmap中的key/value是如下图这样散布的： 其中dataOffset为bmap构造的大小。 漏了一个问题：当查找到所有桶发现没有可插入地位时，阐明所有的桶都满了，须要申请一个溢出桶（可能是事后申请好的，也可能须要从新申请），并且将溢出桶接到以后bucket的前面（如果已有溢出桶则为最初一个溢出桶的前面） map的删除map的删除调用的时mapdelete函数。 删除的逻辑绝对比较简单，大多函数在赋值操作中曾经用到过，所以这里只列除了一些特有的代码（删除数据）。 map的查问map的查问调用的是mapaccess函数。 查问这里次要有一个在扩容过程中查问时须要确认以后key是否曾经迁徙到新的bucket中。次要是通过bmap.tophash来确认。 map的扩容map的扩容有量中状况： 第一种：容量有余，“以后容量+1”之后计算出来扩容因子超出了规定值，即overLoadFactr函数返回true； 第二种：溢出桶过多。溢出桶数量 ≥ （B&15）。 注：这里的扩容因子的规定值是一个定值，是通过教训得出的论断，咱们不做探讨。 当是第一种扩容时，会将map容量扩充一倍。如果是第二种状况则代表可能是空的kv占用的空间过多，这次的扩容不会拓展空间，buckets的数量和原来是一样的然而会对map中的kv进行整顿，去除空的kv。 map的扩容只是将底层数组扩充了一倍，并没有进行数据的转移，数据的转移是在扩容后逐渐进行的，在迁徙的过程中每进行一次赋值（access或者delete）会至多做一次迁徙工作。 map的迁徙在map的赋值与删除中咱们都有说道迁徙，这是扩容后的一部分，迁徙的根底构造是evacDst数据结构如下： 整个迁徙的流程如下： 注： 这里只是简略的举例子，理论中hash值不能够小于5，因为小于5的hash都被用于tophash的标识。 ...

一、容器之Map汇合汇合体系的源码中，Map中的HashMap的设计堪称最经典，波及数据结构、编程思维、哈希计算等等，在日常开发中对于一些源码的思维进行参考借鉴还是很有必要的。 根底：元素增查删、容器信息；进阶：存储构造、容量、哈希；API体系 在整个Map和Set的API体系中，最重要的就是HashMap的实现原理： HashMap：基于哈希表治理元素；LinkedHashMap：基于HashMap和双向链表；HashSet：底层保护HashMap构造；LinkedHashSet：继承HashSet，双向链表；所以Map和Set的系列中，除非凡API之外，基本原理都依赖HashMap，只是在各自具体实现时，实用于不同特点的元素治理。 二、数据结构在看HashMap之前，先了解一种数据结构：数组+链表的构造。 基于数组治理元素的地位，元素的存储造成链表构造，既然是链表那么就能够是单双向的构造，这须要针对具体的API去剖析，通过这个构造能够失去几个要害信息： 扩容：基于数组则面对扩容问题；链表：造成链表构造的机制；哈希：哈希值计算与抵触解决；三、HashMap详解1、构造封装既然下面简略形容了数组+链表的构造，那么从源码角度看看是如何封装的： transient Node<K,V>[] table;在HashMap中数组构造的变量命名为table（表），并且是基于Node<K,V>的节点： static class Node<K,V> implements Map.Entry<K,V> { final int hash; final K key; V value; Node<K,V> next;}实现Map.Entry接口，并定义节点的构造变量，和节点本身的相干办法。 2、构造方法在晓得HashMap中的根底构造后，能够看其相干的构造方法，初始化哪些变量： 无参结构 public HashMap() { this.loadFactor = DEFAULT_LOAD_FACTOR;}float DEFAULT_LOAD_FACTOR = 0.75f;this.loadFactor = DEFAULT_LOAD_FACTOR;实际上还要关注一个外围参数： static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 16即数组默认的初始化容量DEFAULT_INITIAL_CAPACITY为16，扩容的阈值loadFactor为0.75，即示意当数组中元素达到12个便会进行扩容操作。 有参结构 当然也能够通过有参构造方法去设置两个参数：即容量和扩容的阈值： public HashMap(int initialCapacity, float loadFactor) ;通过两个构造方法的源码可知：当间接创立新的HashMap的时候，不会立刻对哈希数组进行初始化，然而能够对要害变量做自定义设置。 3、装载元素顺着HashMap的应用办法，看元素增加： public V put(K key, V value) { return putVal(hash(key), key, value, false, true);}在put的时候并没有做过多间接操作，而是调用两个要害办法： ...

什么是TreeMaptreemap是java.util.Map的一个实现类，TreeMap实现SortedMap接口，可能把它保留的记录依据键排序，默认是按键值的升序排序，也能够指定排序的比拟器，当用Iterator遍历TreeMap时，失去的记录是排过序的。如果应用排序的映射，倡议应用TreeMap。在应用TreeMap时，key必须实现Comparable接口或者在结构TreeMap传入自定义的Comparator，否则会在运行时抛出java.lang.ClassCastException类型的异样。 对于java.lang.ClassCastException异样通常遇到这个异样的起因是强制类型转换时报错，在强制类型转换时，须要留神，父类援用指向的对象的类型是子类的时候才能够进行强制类型转换，如果父类援用指向的对象的类型不是子类的时候将产生java.lang.ClassCastException异样。 Animal a1 = new Dog(); // 1Animal a2 = new Cat(); // 2 Dog d1 = (Dog)a1; //3Dog d2 = (Dog)a2; //4在这个demo中，第三行能够进行强转，然而第四行会抛出java.lang.ClassCastException异样，因为a2是animal，然而具体实现类型是cat，不能间接强转为dog类型。遇到这样的异样的时候如何解决呢？如果你晓得要拜访的的对象的具体类型，间接转换成该类型即可。如果不能确定类型能够通过上面的两种形式进行解决（假如对象为o）：1、通过o.getClass().getName()失去具体的类型，能够通过输入语句输入这个类型，而后依据类型进行进行具体的解决。2、通过if(o instanceof 类型)的语句来判断o的类型是什么。

map是key-value数据结构，又称为字段或者关联数组。相似其余编程语言的汇合 一、根本语法var 变量名 map[keytype]valuetype // map 应用前要make// map 的key不能反复，反复了，以最初的key-value为准// map 的key-value 是无序的var a map[string]stringa = make(map[string]string, 10)a["n1"] = "a"a["n2"] = "b"a["n3"] = "c"二、应用形式先申明，再make var a map[string]stringa = make(map[string]string, 10)申明间接make a := make(map[string]string, 10)申明间接赋值 var a map[string]string = map[string]string{ "n1" : "宋江" "n2" : "卢俊义"}三、增删改查a := make(map[string]string, 10)// 没这个key就减少，有就批改a["n1"] = "aa"delete(a, "n1")val, res := a["n1"] //查找 有res为true，否则为false if res { fmt.Println("找到了") } else { fmt.Println("没到了") }

package com.study.java;import org.junit.jupiter.api.Test;import java.util.HashMap;/** * /----Map:双列数据 存储key-value对的数据 * /----HashMap:作为Map的次要实现类；线程不平安，效率高，存储null的key和value * /----LinkedHashMap:保障遍历map元素时，能够按增加程序实现遍历 * 起因：在原有的HashMap底层构造根底上，增加了一对指针，指向前一个和后一个元素。 * /----TreeMap:保障依照增加的key-value对进行排序，实现排序遍历。此时思考key的天然排序或订制排序 * 底层应用红黑树 * /----Hashtable:作为古老的实现类，线程平安，效率低；不能存储null的key和value * /----Properties:罕用来解决配置文件。key和value都是string类型 * * * HashMap底层：数组+链表 （jdk7及以前） * 数组+链表+红黑树 (jdk8) * * Map构造的了解： * Map中的key：无序的、不可反复的，应用Set存储所有的key key所在的类要重写equals和hashCode办法 * Map中的value：无序的，可反复，应用Collection存储所有的value value所在类要重写equals办法 * 一个键值对：key-value形成一个Entry对象 * Map中的Entry:无序的、不可反复的，应用Set存储所有的entry * * * HashMap的底层实现原理，jdk7为例： * HashMap map = new HashMap(); * 在实例化后，底层创立了长度为16的一维数组Entry[]table * ...... * map.put(k1, v1) * 首先，调用k1所在类的hashcode()计算k1的哈希值，此哈希值通过某种算法计算后，失去Entry数组寄存的地位 * 如果此地位上数据为空，此时K1-v1增加胜利 * 如果此地位上的数据不为空，(意味着此地位上寄存一个或多个数据（以链表模式存在）)，比拟k1和曾经存在的一个或多个数据的哈希值：4 * 如果k1的哈希值和曾经存在的数据哈希值都不雷同，此时K1-v1增加胜利。 状况1 * 如果k1的哈希值和曾经存在的某一个数据（k2-v2）的哈希值雷同，持续比拟：调用k1所在类的equals(k2)办法，比拟： * 如果equals返回false ：增加胜利 状况2 * 如果equals返回true：将v1替换雷同key的value值 * 补充：对于状况2和状况3，此时key1-value1和原来的数据以链表的模式存储 * 在一直增加过程，会波及扩容问题，默认扩容形式：扩容为原来容量的两倍，并将原有的数据复制过去 * * jdk8相较于jdk7在底层实现方面的不同： * 1. new HashMap():底层没有创立一个长度为16的数组 * 2. jdk8 底层的数组是Node[],而非Entry[] * 3. 首次调用put办法时，底层创立长度为16的数组 * 4. jdk7底层构造：数组+链表 jdk8：数组+链表+红黑树 * 当数组的某一个索引地位上的元素以链表模式存在的数据个数 > 8 ，且以后数组的长度 > 64时， * 此时此索引地位上的所有数据改为应用红黑树存储。 * * DEFAULT_INITIAL_CAPACITY :HashMap的默认容量：16 * DEFAULT_LOAD_FACTOR :HashMap的默认加载因子：0.75 * threshold :扩容的临界值：=容量*填充因子：16 * 0.75 => 12 * TREEIFY_THRESHOLD:Bucket 中链表长度大于该默认值，转化为红黑树：8 * MIN_TREEIFY_CAPACITY:桶中的Node被树化时最小的hash表容量 * * * LinkedHashMap的底层实现原理:，增加数据时，还保护了两个援用，记录前一个和后一个数据 * * TreeMap 中增加key-value,要求key必须是由同一个类创立的对象 * //因为要依照key进行排序：天然排序、订制排序 * * Properties:罕用来解决配置文件。key和value都是string类型 */public class MapTest { @Test public void test1() { HashMap hashMap = new HashMap(); hashMap.put(null, 123); hashMap.put(222, "aa"); hashMap.put(223, "bb"); System.out.println(hashMap); } @Test public void test2() { HashMap hashMap = new HashMap(); hashMap.put(null, 123); hashMap.put(222, "aa"); hashMap.put(223, "bb"); System.out.println(hashMap); }}