Map

Map接口

1、实现Map接口的类用来储存键（key）值（value）对

2、Map接口的实现类有HashMap和TreeMap等。

3、Map类中存储的键值对通过键来表示，所以键是不能够重复的。

HashMap的使用

package cn.xjion.pro09; import java.util.Collection; import java.util.HashMap; import java.util.Set; public class TestHashMap { public static void main(String[] args) { // Map接口的特点，无序，键不重复，值可以重复，key无序 // 创建对象 HashMap hm = new HashMap(); // 添加元素 hm.put("helloA", 1001);//值会自动装箱，Integer类型 hm.put("helloB", 1002); hm.put("helloC", 1003); hm.put("helloD", 1005); hm.put("helloA", 1005);//集合中的key值补鞥呢重复，如果重复，将进行值的覆盖 System.out.println("集合中 的元素个数："+hm.size()); System.out.println("集合是否为空:"+hm.isEmpty()); System.out.println("集合"+hm); System.out.println("删除："+hm.remove("helloA")); System.out.println("集合"+hm); // 判断集合中是否有某一个元素 System.out.println(hm.containsKey("helloB")+"\t\t"+hm.containsKey("helloA")); // 判断元素中是否有某一个值 System.out.println(hm.containsValue(1002)+"\t\t"+hm.containsValue(2001)); // 获取元素的值 System.out.println(hm.get("helloA")+"\t\t"+hm.get("helloC")); // 获取所有key的集合 Set set = hm.keySet(); // 遍历 for (Object object : set) { System.out.println(object); } // 获取所有的value值的集合 System.out.println("————————————————————————"); Collection coll = hm.values(); for (Object object : coll) { System.out.println(object); } System.out.println("————————————————————————"); // 获取所有的key-value的关系集合 Set entry = hm.entrySet(); for (Object object : entry) { System.out.println(object); } } }

HashMap与HashTable的去区别

1、版本不同HashMap是JDK1.2，HashTable是JDK1.0.

2、HashMap继承了AbstractMap，实现了Map接口，而HashTable继承的是Dictionary实现Map接口

3、HashMap允许null值和null键，但key只能有一个，HashTable不允许有null值和null键

4、HashMap是线程不同步的（效率高，安全性低）

HashTable底层实现原理

哈希表（HashTable）的结构和特点：

特点：快，特别快，无比的快

结构：结构有多重

最流行和容易被人理解的：顺序表+链表

 

哈希表是如何添加数据的：

1、计算哈希码（调用hashcode(),结构是一个int值，整数的哈希码取自身）

2、计算在哈希表中的存储位置y = l(x) = x x:哈希码 k(x)函数 y:在哈希表中的存储位置

3、如何减少冲突

一半情况下，装填因子去经验值0.5 HashMap中装填因子为0.75

4、哈希函数的选择

直接定址法  平方取中法  除留取余法（y = x % 11）查询相关资料

JDK1.8开始，当链表的个数>=8时，就会将链表转为红黑树，目的是为了减少查询比较的次数

二叉树和红黑树

二叉查找、搜索、排序树 BST

1、是一颗空树

2、二叉树：

（1）若它的左子树不空，则左子树上所有节点的值均小于它的根节点值

（2）右子树上所有节点的值均大于它的根节点的值

（3）它的左、右子树也分别为二叉排序树

平衡二叉树 自平衡二叉查找树

1、它是一棵空树

2、它的左右两个字数的高度差（平衡因子）的绝对值不会超过1

平衡二叉树：每个节点的平衡因子都为1、-1、0的二叉排序树。

平衡二叉树的目的是为了减少二叉查找树层次，提高查找速度。

红黑树

它是一种平衡二叉树。红黑树的每个节点上都有存储位表示节点的颜色，可以是红或黑。

红黑树的特性：

1、每个节点要么是黑色要么是红色。

2、根节点是黑色。

3、每个叶子节点（空节点、NIL）是黑色。

4、如果一个节点是红色 的，它的子节点必须是黑色的。

5、从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。

6、确保没有一条路径会比其他路径长出两倍、因此，红黑树是相对接近平衡的二叉树。

TreeMap的使用和底层实现

TreeMap的使用

Key的特点：唯一的升序的

底层数据结构：红黑树

package cn.xjion.pro09; import java.util.TreeMap; public class TestTreeMap { /** * TreeMap的底层实现 * private final Comparator<? super K> comparator;//外部比较器，用于比较大小的 * private transient Entry<K,V> root; //代表的是树根 * public TreeMap() { comparator = null; } 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; //如果外部比较器不等于null,说明外部比较器存在 if (cpr != null) { do { parent = t; //把root赋给父节点 cmp = cpr.compare(key, t.key); //调用外部比较器的比较方法开始比大小，结果是一个int类型的值 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; //root赋给父节点 cmp = k.compareTo(t.key); //调用内部比较器的比较大小的方法，比较结果为int类型 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; } */ public static void main(String[] args) { //创建集合对象 TreeMap treeMap = new TreeMap(); //添加数据 treeMap.put("hello", 123); treeMap.put("world1", 456); treeMap.put("hello11", 789); treeMap.put("java", 1000); System.out.println("集合中元素的个数:" + treeMap.size()); System.out.println(treeMap); System.out.println(treeMap.containsKey("hello")+"\t"+treeMap.containsKey("sql")); System.out.println(treeMap.containsValue(789)+"\t"+treeMap.containsValue(1002)); System.out.println(treeMap.get("java")); } } package cn.xjion.pro09; import java.util.Comparator; //编写一个外部比较器的实现类，用于实现根据英文字母的个数进行升降比较 public class CompareLength implements Comparator{ @Override public int compare(Object o1, Object o2) { //向下类型转换 String s1 = (String)o1; String s2 = (String)o2; return s1.length()-s2.length(); } //创建外部比较器对象，定义比较规则 Comparator comLength = new CompareLength(); TreeMap treeMap = new TreeMap(comLength); }