>Java >java지도 시간 >Java 해시 테이블 및 정렬된 목록을 구현하는 방법

Java 해시 테이블 및 정렬된 목록을 구현하는 방법

王林
王林앞으로
2023-04-18 11:07:02863검색

    해시 테이블(HashMap)

    해시 쿼리의 시간 복잡도는 O(1)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).我们可以看出,在我们从hashmap里面查询或者操作某些值的话,是以值的形式去传递和匹配的,而不是以内存地址的形式去匹配。

    按址传递

    如果是非原生的类型的话,以内存地址的形式传递。例如:

    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

    内存大小比较

    基础类型,一条记录的内存大小是Key的大小加上Value的大小。

    非基础类型, 一条记录的内存大小是 两个地址的大小, 一个地址8字节,key和value 共16字节

    如果是 基础类型和非基础类型的混合类型的话,就是各自按照各自的方式计算

    有序表(TreeMap)

    • 有序表会根据key的大小进行 升序排列 ,我们可以用他来做hashmap中的所有操作,并且扩展出了,查找第一个key或者最后一个key的操作,也扩展出了查找小于某个区间的最大值和大于某个区间的最小值

    • 所有操作时间复杂度都是O(logn)

      값으로 전달
      Character, Short, Integer , Long, Float, Double, String, Boolean, java에서 해시 테이블은 주소 형식이 아닌 값 형식으로 내부적으로 전달됩니다.
    • 예:

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

    • // 출력 결과
    // a==b = false

    // a.equals(b) = true

    // intMap.get(a) = 111
    // intMap.get ( b) = 111



    위의 경우 a! = b이지만 intMap.get(a) == intMap.get(b)일 수 있습니다. 해시맵에서 특정 값을 쿼리하거나 연산할 때 메모리 주소 형식이 아닌 값 형식으로 전달되고 일치되는 것으로 나타났습니다.

    주소로 전달

    Native 유형이 아닌 경우 메모리 주소 형태로 전달됩니다. 예:
    //        存放非基础类型
    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; 
        }
    }


    //Output result
    //map.containsKey(node1) = true
    //map.containsKey(node2) = false
    메모리 크기 비교
    기본 유형, 1 레코드 메모리 크기는 Key 크기에 Value 크기를 더한 값입니다.

    기본형이 아닌 경우 레코드의 메모리 크기는 주소 2개 크기이고, 주소 1개는 8바이트, 키와 값의 합은 16바이트입니다. 계산 방법 🎜🎜Ordered 목록(TreeMap)🎜
      🎜🎜주문된 목록은 키의 크기에 따라 오름차순으로 정렬되며 이를 사용하여 hashmap 코드의 모든 작업>을 만들 수 있습니다. 첫 번째 키나 마지막 키를 찾는 연산까지 확장되었고, 일정 간격보다 작은 최대값과 특정 간격보다 큰 최소값을 찾는 연산까지 확장되었습니다🎜🎜🎜🎜모든 연산의 시간 복잡도 모두 <code>O(logn) 수준입니다. 🎜🎜🎜🎜그러나 키가 기본 유형이 아닌 경우에는 직접 정렬할 수 없으며 해당 유형에는 정렬 인터페이스를 구현하고 정렬 기능이 있어야 합니다. 또는 new treeMap🎜🎜🎜🎜Storage 기본 유형 연산🎜rrreee🎜🎜//출력 결과는 다음과 같습니다🎜//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🎜🎜🎜기본이 아닌 유형 저장 작전🎜rrreee

    위 내용은 Java 해시 테이블 및 정렬된 목록을 구현하는 방법의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!

    성명:
    이 기사는 yisu.com에서 복제됩니다. 침해가 있는 경우 admin@php.cn으로 문의하시기 바랍니다. 삭제