How to implement Java hash table and ordered list

Hash table (HashMap)

The time complexity of hash query is O(1)

Pass by value

Character, Short, Integer, Long, Float, Double, String, Boolean, in java the hash table is passed internally in the form of value, not in the form of an address transfer.

For example:

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

// Output result
// a==b = false
// a.equals(b) = true
/ / intMap.get(a) = 111
// intMap.get(b) = 111

In the above case, a!= b, but intMap.get(a) == intMap.get(b). We can see that when we query or operate certain values ​​​​from the hashmap, they are passed and matched in the form of values, not in the form of Memory address format to match.

Pass by address

If it is a non-native type, it will be passed in the form of a memory address. For example:

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

//Output result
//map.containsKey(node1) = true
//map.containsKey(node2) = false

Memory size comparison

Basic type, the memory size of a record is the size of the Key plus the size of the Value.

Non-basic type, the memory size of a record is the size of two addresses, one address is 8 bytes, key and value are 16 bytes in total

If it is a basic type and a non-basic type For mixed types, each calculates it in its own way.

Ordered list (TreeMap)

• The ordered list will be arranged in ascending order according to the size of the key. We can use It does all the operations in hashmap, and extends it to the operation of finding the first key or the last key, as well as the search for the maximum value smaller than a certain interval and larger than a certain interval. The minimum value

• The time complexity of all operations is O(logn) level.

• But if the key is a non-basic type, it cannot be sorted directly. The type needs to implement the sorting interface and have the sorting function. Or pass in the comparison method when new treeMap

Storage basic type operation

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

//The output result is as follows
//treeMap.containsKey( 3) = true
//treeMap.containsKey(6) = false
//treeMap.get(3) = I am 3
//treeMap.get(3) = He is 3
//treeMap.get(3) = null
//treeMap.firstKey() = 0
//treeMap.lastKey() = 9
//treeMap.floorKey(5) = 5
//treeMap.floorKey(6) = 5
//treeMap.ceilingKey(4) = 5

Storage non-basic types for operations

//        存放非基础类型
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; 
    }
}

The above is the detailed content of How to implement Java hash table and ordered list. For more information, please follow other related articles on the PHP Chinese website!