【Java】哈希表 VS 有序表

1、哈希表

1. 哈希表在使用层面上可以理解为一种集合结构
2. 如果只有 key，没有伴随数据value，可以使用 HashSet 结构
3. 如果既有key，又有伴随数据value，可以使用 HashMap 结构
4. 有无伴随数据，是 HashMap 和 HashSet 唯一的区别，实际结构是一回事
5. 使用哈希表增(put)、删（remove）、改（put）和 查（get）的 *** 作，可以认为时间复杂度为 O ( 1 ) O(1) O(1)，但是常数时间比较大
6. 放入哈希表的东西，如果是基础类型（原生类型），内部按值传递，内存占用是这个东西的大小
7. 放入哈希表的东西，如果不是基础类型（自定义的类型），内部按引用传递，内存占用是8字节

2、有序表

1. 有序表在使用层面上可以理解为一种集合结构

2. 如果只有key，没有伴随数据value，可以使用 TreeSet 结构

3. 如果既有key，又有伴随数据value，可以使用 TreeMap 结构

4. 有无伴随数据，是 TreeSet 和 TreeMap 唯一的区别，底层的实际结构是一回事

5. 有序表把 key 按照顺序组织起来，而哈希表完全不组织

6. 红黑树、AVL树、size-balance-tree 和跳表等都属于有序表结构，只是底层具体实现不同

7. 放入如果是基础类型，内部按值传递，内存占用就是这个东西的大小

8. 放入如果不是基础类型，内部按引用传递，内存占用是8字节

9. 不管是什么底层具体实现，只要是有序表，都有以下固定的基本功能和固定的时间复杂度

   1. void put(K key, V value)

      将一个 (key, value) 记录加入到表中，或者将 key 的记录更新成 value

   2. V get(K key)

      根据给定的 key，查询 value 并返回

   3. void remove(K key)

      移除 key 的记录

   4. boolean containsKey(K key)
      询问是否有关于 key 的记录

3、时间复杂度

哈希表在使用时，增删改查时间复杂度都是 O ( 1 ) O(1) O(1)

有序表在使用时，比哈希表功能多，时间复杂度都是 O ( l o g N ) O(logN) O(logN)

4、使用示例

import java.util.HashMap;
import java.util.HashSet;
import java.util.TreeMap;

public class HashMapAndSortedMap {

	public static class Node {
		public int value;

		public Node(int v) {
			value = v;
		}
	}

	public static class Zuo {
		public int value;

		public Zuo(int v) {
			value = v;
		}
	}

	public static void main(String[] args) {
		//===========
		HashMap<Integer, String> test = new HashMap<>();
		Integer a = 19000000;
		Integer b = 19000000;
		System.out.println(a == b); //false，因为按引用传递
        
        //===========
		test.put(a, "我是3");
		System.out.println(test.containsKey(b)); //true,哈希表中按值传递，因为a和b的值相同，哈希表仅以值为key

		//===========
		Zuo z1 = new Zuo(1);
		Zuo z2 = new Zuo(1);
		HashMap<Zuo, String> test2 = new HashMap<>();
		test2.put(z1, "我是z1");
		System.out.println(test2.containsKey(z2));//false，非原生类型，哈希表中按引用传递

		// UnSortedMap
		HashMap<Integer, String> map = new HashMap<>();
		map.put(1000000, "我是1000000");
		map.put(2, "我是2");
		map.put(3, "我是3");
		map.put(4, "我是4");
		map.put(5, "我是5");
		map.put(6, "我是6");
		map.put(1000000, "我是1000001");

		System.out.println(map.containsKey(1));
		System.out.println(map.containsKey(10));

		System.out.println(map.get(4));
		System.out.println(map.get(10));

		map.put(4, "他是4");
		System.out.println(map.get(4));

		map.remove(4);
		System.out.println(map.get(4));

		// key
		HashSet<String> set = new HashSet<>();
		set.add("abc");
		set.contains("abc");
		set.remove("abc");

		// 哈希表，增、删、改、查，在使用时，O（1）

		System.out.println("=====================");

		Integer c = 100000;
		Integer d = 100000;
		System.out.println(c.equals(d));

		Integer e = 127; // - 128 ~ 127
		Integer f = 127;
		System.out.println(e == f);

		HashMap<Node, String> map2 = new HashMap<>();
		Node node1 = new Node(1);
		Node node2 = node1;
		map2.put(node1, "我是node1");
		map2.put(node2, "我是node1");
		System.out.println(map2.size());

		System.out.println("======================");

		// TreeMap 有序表：接口名
		// 红黑树、avl、sb树、跳表
		// O(logN)
		System.out.println("有序表测试开始");
		TreeMap<Integer, String> treeMap = new TreeMap<>();

		treeMap.put(3, "我是3");
		treeMap.put(4, "我是4");
		treeMap.put(8, "我是8");
		treeMap.put(5, "我是5");
		treeMap.put(7, "我是7");
		treeMap.put(1, "我是1");
		treeMap.put(2, "我是2");

		System.out.println(treeMap.containsKey(1)); //true
		System.out.println(treeMap.containsKey(10)); // false

		System.out.println(treeMap.get(4)); //我是4
		System.out.println(treeMap.get(10)); //null

		treeMap.put(4, "他是4");
		System.out.println(treeMap.get(4)); //他是4

		// treeMap.remove(4);
		System.out.println(treeMap.get(4)); //null

		System.out.println("新鲜：");

		System.out.println(treeMap.firstKey()); //1 最小的key
		System.out.println(treeMap.lastKey()); //8 最大的key
		// <= 4
		System.out.println(treeMap.floorKey(4)); //4
		// >= 4 
		System.out.println(treeMap.ceilingKey(4)); //4
		// O(logN)

        //会报错，自定义类型必须自己实现比较器，定义比较方法
        //TreeMap zuoMap = new TreeMap<>(/*传入比较器*/);
        //zuoMap.put(z1, "我是z1");
        //zuoMap.put(z2, "我是z2");
	}
}