Javaハッシュテーブルと順序付きリストの実装方法

ハッシュ テーブル (HashMap)

ハッシュ クエリの時間計算量は 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). ハッシュマップから特定の値をクエリまたは操作すると、それらは値の形式ではなく、値の形式で渡され、照合されることがわかります。一致するメモリアドレス形式の形式で。

アドレスで渡す

非ネイティブ型の場合は、メモリ アドレスの形式で渡されます。例:

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

メモリ サイズの比較

基本タイプ。レコードのメモリ サイズは、キーのサイズに値のサイズを加えたものです。

非基本型の場合、レコードのメモリサイズはアドレス2つ分のサイズ、1アドレスは8バイト、キーと値の合計は16バイトです

基本型の場合混合型の場合、それぞれが独自の方法で計算します。

順序付きリスト (ツリーマップ)

• 順序付きリストは昇順に配置されます。 hashmap 内のすべての操作を実行し、最初のキーまたは最後のキーを見つける操作や最大値の検索まで拡張します。一定の間隔より小さく、一定の間隔より大きい最小値

• すべての操作の時間計算量は O(logn) レベルです。

• ただし、キーが非基本型の場合は直接ソートできないため、ソートインターフェイスを実装し、ソート機能を持たせる必要があります。または、新しい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 中国語 Web サイトの他の関連記事を参照してください。