search
HomeJavajavaTutorialHow 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!

    Statement
    This article is reproduced at:亿速云. If there is any infringement, please contact admin@php.cn delete
    How do I use Maven or Gradle for advanced Java project management, build automation, and dependency resolution?How do I use Maven or Gradle for advanced Java project management, build automation, and dependency resolution?Mar 17, 2025 pm 05:46 PM

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

    How do I create and use custom Java libraries (JAR files) with proper versioning and dependency management?How do I create and use custom Java libraries (JAR files) with proper versioning and dependency management?Mar 17, 2025 pm 05:45 PM

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

    How do I implement multi-level caching in Java applications using libraries like Caffeine or Guava Cache?How do I implement multi-level caching in Java applications using libraries like Caffeine or Guava Cache?Mar 17, 2025 pm 05:44 PM

    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

    How can I use JPA (Java Persistence API) for object-relational mapping with advanced features like caching and lazy loading?How can I use JPA (Java Persistence API) for object-relational mapping with advanced features like caching and lazy loading?Mar 17, 2025 pm 05:43 PM

    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]

    How does Java's classloading mechanism work, including different classloaders and their delegation models?How does Java's classloading mechanism work, including different classloaders and their delegation models?Mar 17, 2025 pm 05:35 PM

    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

    See all articles

    Hot AI Tools

    Undresser.AI Undress

    Undresser.AI Undress

    AI-powered app for creating realistic nude photos

    AI Clothes Remover

    AI Clothes Remover

    Online AI tool for removing clothes from photos.

    Undress AI Tool

    Undress AI Tool

    Undress images for free

    Clothoff.io

    Clothoff.io

    AI clothes remover

    AI Hentai Generator

    AI Hentai Generator

    Generate AI Hentai for free.

    Hot Article

    R.E.P.O. Energy Crystals Explained and What They Do (Yellow Crystal)
    4 weeks agoBy尊渡假赌尊渡假赌尊渡假赌
    R.E.P.O. Best Graphic Settings
    4 weeks agoBy尊渡假赌尊渡假赌尊渡假赌
    R.E.P.O. How to Fix Audio if You Can't Hear Anyone
    4 weeks agoBy尊渡假赌尊渡假赌尊渡假赌
    R.E.P.O. Chat Commands and How to Use Them
    4 weeks agoBy尊渡假赌尊渡假赌尊渡假赌

    Hot Tools

    SAP NetWeaver Server Adapter for Eclipse

    SAP NetWeaver Server Adapter for Eclipse

    Integrate Eclipse with SAP NetWeaver application server.

    Dreamweaver CS6

    Dreamweaver CS6

    Visual web development tools

    Zend Studio 13.0.1

    Zend Studio 13.0.1

    Powerful PHP integrated development environment

    EditPlus Chinese cracked version

    EditPlus Chinese cracked version

    Small size, syntax highlighting, does not support code prompt function

    MinGW - Minimalist GNU for Windows

    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.