Java哈希表和有序表怎么實(shí)現(xiàn)

本文小編為大家詳細(xì)介紹“Java哈希表和有序表怎么實(shí)現(xiàn)”，內(nèi)容詳細(xì)，步驟清晰，細(xì)節(jié)處理妥當(dāng)，希望這篇“Java哈希表和有序表怎么實(shí)現(xiàn)”文章能幫助大家解決疑惑，下面跟著小編的思路慢慢深入，一起來學(xué)習(xí)新知識(shí)吧。

哈希表（HashMap）

hash查詢的時(shí)間復(fù)雜度是O(1)

按值傳遞

Character，Short,Integer,Long， Float，Double，String，Boolean，在java當(dāng)中哈希表內(nèi)部以值的形式傳遞，而不是一地址的形式傳遞。

例如：

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));

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

由上邊的案例中 a!= b,但是intMap.get(a) == intMap.get(b).我們可以看出，在我們從hashmap里面查詢或者操作某些值的話，是以值的形式去傳遞和匹配的，而不是以內(nèi)存地址的形式去匹配。

按址傳遞

如果是非原生的類型的話，以內(nèi)存地址的形式傳遞。例如：

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));

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

內(nèi)存大小比較

基礎(chǔ)類型，一條記錄的內(nèi)存大小是Key的大小加上Value的大小。

非基礎(chǔ)類型， 一條記錄的內(nèi)存大小是 兩個(gè)地址的大小， 一個(gè)地址8字節(jié)，key和value 共16字節(jié)

如果是 基礎(chǔ)類型和非基礎(chǔ)類型的混合類型的話，就是各自按照各自的方式計(jì)算

有序表（TreeMap）

• 有序表會(huì)根據(jù)key的大小進(jìn)行 升序排列 ，我們可以用他來做hashmap中的所有操作，并且擴(kuò)展出了，查找第一個(gè)key或者最后一個(gè)key的操作，也擴(kuò)展出了查找小于某個(gè)區(qū)間的最大值和大于某個(gè)區(qū)間的最小值

• 所有操作時(shí)間復(fù)雜度都是O(logn)級(jí)別。

• 但是如果key是非基礎(chǔ)類型的話，并不能直接排序，需要該類型實(shí)現(xiàn)了排序接口，有可排序功能?；蛘咴趎ew treeMap的時(shí)候傳入比較方法

存放基礎(chǔ)類型操作

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));

//輸出結(jié)果如下
//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

存放非基礎(chǔ)類型進(jìn)行操作

//        存放非基礎(chǔ)類型
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哈希表和有序表怎么實(shí)現(xiàn)”文章已經(jīng)介紹完畢，想要掌握這篇文章的知識(shí)點(diǎn)還需要大家自己動(dòng)手實(shí)踐使用過才能領(lǐng)會(huì)，如果想了解更多相關(guān)內(nèi)容的文章，歡迎關(guān)注億速云行業(yè)資訊頻道。