业内经常说的一句话是不要重复造轮子, 但是有时候, 只有自己造一个轮子了, 才会深刻明白什么样的轮子适合山路, 什么样的轮子适合平地!
往期章节:
JAVA 基础第一章 - 初识 java
JAVA 基础第二章 - java 三大特性: 封装, 继承, 多态
JAVA 基础第三章 - 类与对象, 抽象类, 接口
JAVA 基础第四章 - 集合框架 Collection 篇
在上一章节中, 我们讲了集合框架的 Collection 部分, 下面我们来讲一下 Map 接口
我们再看一下集合框架的结构图
map 接口的实现类大致有 HashMap,LinkedHahMap,TreeMap,HashTable 四类.
Map
从这个名字上我们可以知道是 "地图, 映射" 的意思.
map 集合使用键 (key) 值(value)来保存数据, 其中值 (value) 可以重复, 但键 (key) 必须是唯一, 也可以为空, 但最多只能有一个 key 为空.
HashMap
对于 hashMap, 我们需要从名字中的 hash 入手, 去分析他, hash, 我们经常叫做哈希表又或者叫做散列函数.
在 JDK 中, Object 的 hashcode 方法是本地方法, 也就是用 c 语言或 c++ 实现的, 该方法直接返回对象的 内存地址.
先看一张图
如上图中的结构过程整个形成过程大致如下:
1, 假如我们先插入一个键值对, 然后进行 hash 后, 存放在了数组的 1 号位置;
2, 然后我们再插入一个键值对 , 经过 hash 后, 存在了 4 号位置,;
3, 再然后我们又插入了一个键值对, 这个时候很不幸, 与 1 号位置冲突, 然后这个时候会在 1 号位置之后追加一个链表, 让 1 号位置的 Entry 中的 next 指向这次最新追加的这一个键值对, 以此类推;
从上图中我们大概可以了解到, 整个的 HashMap 的数据结构就是数组 + 链表(在 jdk1.8 中确切的说是 Node 对象, 只不过 Node 实现了 Entry 接口), 我们先看看 Node 类的代码:
从上面的代码我们可以看出主要有 4 个属性, key value, hash, 以及再包含一个自身的类对象 Node~ 这部分其实和我们上一节讲过的 LinkedList 的数据结构很像
当我们在代码中我们会调用 put 方法, 源码如下:
- /**
- * Associates the specified value with the specified key in this map.
- * If the map previously contained a mapping for the key, the old
- * value is replaced.
- *
- * @param key key with which the specified value is to be associated
- * @param value value to be associated with the specified key
- * @return the previous value associated with <tt>key</tt>, or
- * <tt>null</tt> if there was no mapping for <tt>key</tt>.
- * (A <tt>null</tt> return can also indicate that the map
- * previously associated <tt>null</tt> with <tt>key</tt>.)
- */
- public V put(K key, V value) {
- return putVal(hash(key), key, value, false, true);
- }
从注释中我们可以了解大意:"关联一个指定的值和键在这个 map 如果 map 显然已经包含了这个键的映射, 那么旧值就会被替代"
在这个代码中继续调用 putval 方法, 我们继续看源码:
- /**
- * 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) {
- 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.put 和相关的方法
从第 14 行代码开始意思是, 这个 map 如果是空的, 那先初始化一个数组, 然后再 new 一个 Node 对象, 放入数组中, 具体的位置根据数组的长度和 hash 的 "与" 值确定 ;
如果已经有元素存在 map 中, 则代码从 19 行开始执行, 对于这块大致意思就是, 如果已经存在相同的 hashcode , 那么会判断键是否相同, 如果也相同则替换原有的值.
另外关于 hashMap 的扩容, 我们需要了解的是默认的容量是 16 重载因子是 0.75 什么意思呢?
就是说当集合中的数据量大小达到了门限值 16*0.75=12, 那再添加元素进去, 就会对当前的集合进行扩容, 扩容为原来的 2 倍.
注意, 这里是根据门限值进行扩容也就是 12, 而不是总容量 16.
TreeMap
根据名字我们可以知道这是一个和树有关的 map, 关于 treemap 的结构图大致如下:
从上图中可以大概了解到, treemap 的实现底层是红黑树, 了解这个的同学相信也就能知道为什么 treemap 是有序的了.
这个图中的每一个节点对象都是 Entry, 他和 hashmap 中的不一样, 而是一个类, 不是接口, 代码如下图所示:
从上图圈中可以了解到, 每一个节点都包含 key,value, 以及 Entry 类型的 left,right,parent 属性
上述结构图形成过程大致描述如下:
1, 我们先插入一个键值对, 键为 2;
2, 再插入一个键为 1, 这个时候, 会将这个键值对放在上一个的左子节点部分;
3, 再插入一个 3, 这个时候, 会将他放在第一个节点的右子节点部分;
4, 如果再插入一个 4, 那这个时候, 会把前面 3 个整体作为他的左子节点, 以此类推;
我们再来看看源码:
- /**
- * Associates the specified value with the specified key in this map.
- * If the map previously contained a mapping for the key, the old
- * value is replaced.
- *
- * @param key key with which the specified value is to be associated
- * @param value value to be associated with the specified key
- *
- * @return the previous value associated with {@code key}, or
- * {@code null} if there was no mapping for {@code key}.
- * (A {@code null} return can also indicate that the map
- * previously associated {@code null} with {@code key}.)
- * @throws ClassCastException if the specified key cannot be compared
- * with the keys currently in the map
- * @throws NullPointerException if the specified key is null
- * and this map uses natural ordering, or its comparator
- * does not permit null keys
- */
- 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;
- }
从注释可以了解, 和 hashmap 表达的意思一样, 再看代码中, 如果还没有初始化, 那先进行初始化 root 节点, 如果有指定比较器, 那就根据指定的比较器, 进行比较.
然后后面的代码就是根据插入的键进行大小的比较, 然后设置各种左右子父节点属性等.
LinkedHahMap
关于 linkedHashMap, 从名字可以知道他是和链表有关系的, 结构图如下所示:
注意图中的灰色箭头, 在这里我们需要和一开始我们讲的 hashmap 中的结构图, 做一个比较, 在 hashmap 中虽然也有链表, 但是我们要知道, 那个链表只是为了解决 hash 冲突, 链表中的元素互相之间没有什么关系, 不代表谁早谁晚, 或者说谁大谁小.
而这里的链表中比 hashmap 多了一个 before 和 after, 如下图:
那么这里的 before 和 after 就确定了插入的顺序先后.
HashTable
关于 hashTable 基本上和 HashMap 结构一致, 不再赘述, 唯一区别就是他是线程安全的, 而且不允许 null value, 如果有直接抛出异常
为什么是线程安全的? 我们看如下源码:
- /**
- * Maps the specified <code>key</code> to the specified
- * <code>value</code> in this hashtable. Neither the key nor the
- * value can be <code>null</code>. <p>
- *
- * The value can be retrieved by calling the <code>get</code> method
- * with a key that is equal to the original key.
- *
- * @param key the hashtable key
- * @param value the value
- * @return the previous value of the specified key in this hashtable,
- * or <code>null</code> if it did not have one
- * @exception NullPointerException if the key or value is
- * <code>null</code>
- * @see Object#equals(Object)
- * @see #get(Object)
- */
- public synchronized V put(K key, V value) {
- // Make sure the value is not null
- if (value == null) {
- throw new NullPointerException();
- }
- // Makes sure the key is not already in the hashtable.
- Entry<?,?> tab[] = table;
- int hash = key.hashCode();
- int index = (hash & 0x7FFFFFFF) % tab.length;
- @SuppressWarnings("unchecked")
- Entry<K,V> entry = (Entry<K,V>)tab[index];
- for(; entry != null ; entry = entry.next) {
- if ((entry.hash == hash) && entry.key.equals(key)) {
- V old = entry.value;
- entry.value = value;
- return old;
- }
- }
- addEntry(hash, key, value, index);
- return null;
- }
从上面的方法中加上的 synchronized 关键词, 我们就可以知道了.
另外要注意的是 hashTable 已经不建议使用了, 取而代之的是 ConcurrentHashMap , 因为他既保证了线程的安全性, 又进一步提高了, 效率.
四个实现类的异同:
1. HashMap 是基于哈希表 (hash table) 实现, 其 keys 和 values 都没有顺序.
2. TreeMap 是基于红黑树 (red-black tree) 实现, 按照 keys 排序元素, 可以指定排序规则, 如果不指定则按照自然排序.
3. LinkedHashMap 是基于哈希表 (hash table) 实现, 按照插入顺序排序元素.
4. Hashtable 区别与 HashMap 的地方只有, 它是同步的(synchronized), 因此性能较低些. 为了性能, 在线程安全的代码中, 优先考虑使用 HashMap.
Map 的遍历
对于 map 的遍历大致有以下 3 种方式:
- 1 // 第 1 种只遍历键或者值, 通过加强 for 循环
- 2 for(String s1:map.keySet()){// 遍历 map 的键
- 3 System.out.println("键 key :"+s1);
- 4 }
- 5 for(String s2:map.values()){// 遍历 map 的值
- 6 System.out.println("值 value :"+s2);
- 7 }
- 8 9
- 10 // 第 2 种方式 Map.Entry<String, String > 的加强 for 循环遍历输出键 key 和值 value
- 11 for(Map.Entry<String, String> entry : map.entrySet()){
- 12 System.out.println("键 key :"+entry.getKey()+"值 value :"+entry.getValue());
- 13 }
- 14 15
- 16 // 第 3 种 Iterator 遍历获取, 然后获取到 Map.Entry<String, String>, 再得到 getKey()和 getValue()
- 17 Iterator<Map.Entry<String, String>> it=map.entrySet().iterator();
- 18 while(it.hasNext()){
- 19 Map.Entry<String, String> entry=it.next();
- 20 System.out.println("键 key :"+entry.getKey()+"value :"+entry.getValue());
- 21 }
比较器
在这里说以下 Comparable , Comparator 2 个接口
Comparable
只有一个方法 compareto, 而且是通过返回的 int 型数值判断大小
1, 比较者大于被比较者(也就是 compareTo 方法里面的对象), 那么返回正整数
2, 比较者等于被比较者, 那么返回 0
3, 比较者小于被比较者, 那么返回负整数
Comparator
Comparator 接口里面有一个 compare 方法, 方法有两个参数 T o1 和 T o2, 是泛型的表示方式, 分别表示待比较的两个对象, 方法返回值和 Comparable 接口一样是 int, 有三种情况:
1,o1 大于 o2, 返回正整数
2,o1 等于 o2, 返回 0
3,o1 小于 o3, 返回负整数
二者之间的区别:
1, 比较方法参数数不同;
2, 后者接口中提供了更多的方法可以供使用;
3, 前者只能和自己比较, 后者可以对其他 2 个类进行比较;
关于集合部分, 到这里我们就全部结束了.
注; 以上源码分析都是基于 jdk1.8
文中若有不正之处, 欢迎批评指正!
来源: https://www.cnblogs.com/JJJ1990/p/10150157.html