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 valueThe 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!

The article discusses using Maven and Gradle for Java project management, build automation, and dependency resolution, comparing their approaches and optimization strategies.

The article discusses creating and using custom Java libraries (JAR files) with proper versioning and dependency management, using tools like Maven and Gradle.

The article discusses implementing multi-level caching in Java using Caffeine and Guava Cache to enhance application performance. It covers setup, integration, and performance benefits, along with configuration and eviction policy management best pra

The article discusses using JPA for object-relational mapping with advanced features like caching and lazy loading. It covers setup, entity mapping, and best practices for optimizing performance while highlighting potential pitfalls.[159 characters]

Java's classloading involves loading, linking, and initializing classes using a hierarchical system with Bootstrap, Extension, and Application classloaders. The parent delegation model ensures core classes are loaded first, affecting custom class loa


Hot AI Tools

Undresser.AI Undress
AI-powered app for creating realistic nude photos

AI Clothes Remover
Online AI tool for removing clothes from photos.

Undress AI Tool
Undress images for free

Clothoff.io
AI clothes remover

AI Hentai Generator
Generate AI Hentai for free.

Hot Article

Hot Tools

SAP NetWeaver Server Adapter for Eclipse
Integrate Eclipse with SAP NetWeaver application server.

Dreamweaver CS6
Visual web development tools

Zend Studio 13.0.1
Powerful PHP integrated development environment

EditPlus Chinese cracked version
Small size, syntax highlighting, does not support code prompt function

MinGW - Minimalist GNU for Windows
This project is in the process of being migrated to osdn.net/projects/mingw, you can continue to follow us there. MinGW: A native Windows port of the GNU Compiler Collection (GCC), freely distributable import libraries and header files for building native Windows applications; includes extensions to the MSVC runtime to support C99 functionality. All MinGW software can run on 64-bit Windows platforms.