哈希表和有序表(简单理解型)

​ 1.哈希表的使用

​ 2.有序表的使用

哈希表的使用HashMap

首先哈希表是按照键值对的方式存储数据的，里面有正常的增删改查的方法，但是它最牛的是：

不管数据量多大，==它的增删改查的时间复杂度都是O（1）！！！！！！！！！！！！！！！！！==

==另一个重要的是它的数据传递方式是按值传递==，不是按照数据地址传递。

只要数据类型是Integer,Double,String,Float,Char都是按值传递，而非原生类型的就不行咯~~

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
package class01;

import com.sun.org.apache.xalan.internal.xsltc.runtime.Node;

import java.util.HashMap;

/**
 * @Auther: ouyy
 * @Date: 2023/5/8 - 05 - 08 - 18:26
 * @Description: class01
 * @version: 1.0
 */
public class Code10_HashMapTreeMap {
    public static class Node{
        public int value;
        public Node(int v){
            value = v;
        }
    }

    //这是一个main方法，是程序的入口：
    public static void main(String[] args) {
        //HashMap的使用
        HashMap<String, String> map = new HashMap<>();
        //HashMap的增删改查
        //(K,V) 表 按照键值对的形式存储，并且是按照值传递而不是按地址传递！！！
        //增加
        map.put("OYY", "我爱OYY");
        //删除，里面穿入的是key
        map.remove("OYY");
        //修改也是put
        map.put("TLL", "TLL好看");
        map.put("TLL", "TLL最好看");
        //查询
        System.out.println(map.get("TLL"));//TLL最好看
        System.out.println(map.containsKey("TLL"));//true
        //按值传递案例
        HashMap<Integer, String> map2 = new HashMap<>();
        map2.put(123, "123");
        Integer a = 123;
        Integer b = 123;
        System.out.println("==\t" + (a == b));//比较的是地址，false
        System.out.println(".equals\t" + a.equals(b));//比较的是值,true
        System.out.println("test a\t" + map2.containsKey(a));//true
        System.out.println("test b\t" + map2.containsKey(b));//true

        Node node1 = new Node(1);
        Node node2 = new Node(1);
        HashMap<Node,String> map3 = new HashMap<>();
        map3.put(node1,"node1");
        System.out.println(map3.containsKey(node1));//true
        System.out.println(map3.containsKey(node2));//false
    }


}

而HashMap的空间占用就是K的大小加上V的大小就是表的字节数啦。

但是如果非原生类型的值比如上面的Node那么HashMap所占空间大小就只是K和V的地址大小总和（小很多）。

（一个地址8字节，共16字节）

有序表TreeMap

有序表里面的存储数据是有序的，也是很正常的增删改查方法，他比HashMap强的是它可以返回最大的Key,最小的，离某个数最近的，那么比HashMap强为什么还要存在HashMap呢？因为TreeMap所有操作的时间复杂度都是O（log N）级别没有HashMap强。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
System.out.println("==============");
        TreeMap<Integer,String> treeMap1 = new TreeMap<>();
        //增加
        treeMap1.put(3,"3");
        treeMap1.put(7,"7");
        treeMap1.put(1,"1");
        treeMap1.put(2,"2");
        treeMap1.put(4,"4");
        treeMap1.put(8,"8");
        //查
        System.out.println(treeMap1.containsKey(7));
        //修改
        treeMap1.put(3,"9");
        System.out.println(treeMap1.get(3));//9
        //删除
        treeMap1.remove(3);
        System.out.println(treeMap1.get(3));//false

        //会按照key排好序，比hashmap多的功能
        System.out.println(treeMap1.firstKey());
        System.out.println(treeMap1.lastKey());
        //返回离3最近的key <=3
        System.out.println(treeMap1.floorKey(3));//2
        //返回离10最近的key <=10,就算没加过也可以
        System.out.println(treeMap1.floorKey(10));//8
        //返回离5最近的key >=5,同样没加过也可以
        System.out.println(treeMap1.ceilingKey(5));

那么如果是非原生类型的怎么用捏？

1
2
3
4
5
6
7
Node node3 = new Node(3);
        Node node4 = new Node(3);
        TreeMap<Node,String> treeMap2 = new TreeMap<>();
        treeMap2.put(node3,"3");
        treeMap2.put(node4,"4");
        //会报错，因为没有声明（需要自己定义比较方法，不然用不了）如何比较两个KEY，那么如何实现呢？未完待续嘿嘿。