首頁  >  文章  >  Java  >  Java哈希表和有序表怎麼實現

Java哈希表和有序表怎麼實現

WBOY
WBOY轉載
2023-04-13 17:31:051344瀏覽

    哈希表(HashMap)

    hash查詢的時間複雜度是O(1)

    按值傳遞

    Character,Short,Integer,Long, Float,Double,String,Boolean,在java當中哈希表內部以值的形式傳遞,而不是一位址的形式傳遞。

    例如:

    HashMap<Integer, String> intMap = new HashMap<>();
    intMap.put(1234567, "111");
    Integer a = 1234567;
    Integer b = 1234567;
    System.out.println("a==b = " + (a == b));
    System.out.println("a.equals(b) = " + a.equals(b));
    System.out.println("intMap.get(a) = " + intMap.get(a));
    System.out.println("intMap.get(b) = " + intMap.get(b));

    // 輸出結果
    // a==b = false
    // a.equals(b) = true
    / / intMap.get(a) = 111
    // intMap.get(b) = 111

    由上邊的案例中 a!= b,但是 intMap.get(a) == intMap.get(b).我們可以看出,在我們從hashmap裡面查詢或操作某些值的話,是以值的形式去傳遞和匹配的,而不是以記憶體位址的形式去匹配。

    按址傳遞

    如果是非原生的類型的話,以記憶體位址的形式傳遞。例如:

    public static class Node {
        private int value;
        public Node(int value) {
            this.value = value;
        }
    }
    HashMap<Node, String> map = new HashMap<>();
    Node node1 = new Node(1);
    Node node2 = new Node(1);
    map.put(node1, "ziop");
    System.out.println("map.containsKey(node1) = " + map.containsKey(node1));
    System.out.println("map.containsKey(node2) = " + map.containsKey(node2));

    //輸出結果
    //map.containsKey(node1) = true
    //map.containsKey(node2) = false

    #記憶體大小比較

    基礎型,一筆記錄的記憶體大小是Key的大小加上Value的大小。

    非基礎類型, 一筆記錄的記憶體大小是兩個位址的大小, 一個位址8位元組,key和value 共16位元組

    如果是基礎型別和非基礎型別的混合類型的話,就是各自按照各自的方式計算

    有序表(TreeMap)

    • #有序表會根據key的大小進行升序排列,我們可以用他來做hashmap中的所有操作,並且擴展出了,查找第一個key或最後一個key的操作,也擴展出了查找小於某個區間的最大值和大於某個區間的最小值

    • 所有運算時間複雜度都是O(logn)等級。

    • 但是如果key是非基礎類型的話,並不能直接排序,需要該類型實作了排序接口,有可排序功能。或是在new treeMap的時候傳入比較方法

    存放基礎類型運算

    TreeMap<Integer, String> treeMap = new TreeMap<>();
    treeMap.put(3,"我是3 ");
    treeMap.put(0,"我是3 ");
    treeMap.put(7,"我是3 ");
    treeMap.put(2,"我是3 ");
    treeMap.put(5,"我是3 ");
    treeMap.put(9,"我是3 ");
    treeMap.put(1,"我是3 ");
    System.out.println("treeMap.containsKey(3) = "+treeMap.containsKey(3));
    System.out.println("treeMap.containsKey(6) = "+treeMap.containsKey(6));
    System.out.println("treeMap.get(3) = "+treeMap.get(3));
    treeMap.put(3,"他是3");
    System.out.println("treeMap.get(3) = "+treeMap.get(3));
    treeMap.remove(3);
    System.out.println("treeMap.get(3) = "+treeMap.get(3));
    treeMap.remove(3);
    System.out.println("treeMap.firstKey() = "+treeMap.firstKey());
    System.out.println("treeMap.lastKey() = "+treeMap.lastKey());
    //        返回 小于等于五 并且最近的 key
    System.out.println("treeMap.floorKey(5) = "+treeMap.floorKey(5));
    System.out.println("treeMap.floorKey(6) = "+treeMap.floorKey(6));
    //        返回 大于等于 4 并且最靠近的值
    System.out.println("treeMap.ceilingKey(4) = "+treeMap.ceilingKey(4));

    //輸出結果如下
    //treeMap.containsKey( 3) = true 
    //treeMap.containsKey(6) = false 
    //treeMap.get(3) = 我是3 
    //treeMap.get(3) = 他是3
    //treeMap.get(3) = null
    //treeMap.firstKey() = 0
    //treeMap.lastKey() = 9
    //treeMap.floorKey(5) = 5
    //treeMap.floorKey(6) = 5
    //treeMap.ceilingKey(4) = 5

    存放非基礎型別做動作

    //        存放非基础类型
    public static void main(String[] args) {
    TreeMap<Node, Integer> treeMap1 = new TreeMap<>();
    Node node3 = new Node(3);
    Node node4 = new Node(4);
    treeMap1.put(node3, 3);
    treeMap1.put(node4, 4);
    System.out.println("treeMap1.firstEntry().getValue() = " + treeMap1.firstEntry().getValue());
    System.out.println("treeMap1.lastEntry().getValue() = " + treeMap1.lastEntry().getValue());
    }
    public static class Node implements Comparable<Node> {
    private int value;
        public Node(int value) {
        this.value = value;
    }
            @Override
        public int compareTo(Node node) {
            return this.value - node.value; 
        }
    }

    以上是Java哈希表和有序表怎麼實現的詳細內容。更多資訊請關注PHP中文網其他相關文章!

    陳述:
    本文轉載於:yisu.com。如有侵權,請聯絡admin@php.cn刪除