openplanning

Hướng dẫn sử dụng Java IdentityHashMap

Xem thêm các chuyên mục:

1- IdentityHashMap

IdentityHashMap<K,V> là một lớp nằm trong nền tảng tập hợp của Java (Java Collection Framework), và thi hành interface Map<K,V>. IdentityHashMap hỗ trợ đầy đủ tất cả các tính năng được đặc tả trong interface Map bao gồm cả các tính năng tuỳ chọn. Về cơ bản IdentityHashMap khá giống với HashMap, chúng cùng sử dụng kỹ thuật băm (hashing technique) để nâng cao hiệu năng truy cập và lưu trữ dữ liệu. Tuy nhiên chúng khác nhau về cách lưu trữ dữ liệu và cách so sánh các khoá (key) với nhau. IdentityHashMap sử dụng toán tử == để so sánh 2 khoá, còn HashMap sử dụng phương thức equals.
public class IdentityHashMap<K,V> extends AbstractMap<K,V>
                     implements Map<K,V>, java.io.Serializable, Cloneable
IdentityHashMap constructors:
IdentityHashMap()
Tạo đối tượng IdentityHashMap rỗng với kích thước tối đa dự kiến mặc định (21).
IdentityHashMap​(int expectedMaxSize)
Tạo đối tượng IdentityHashMap rỗng với kích thước tối đa dự kiến được chỉ định. Việc thêm nhiều hơn expectedMaxSize ánh xạ vào IdentityHashMap sẽ làm cho cấu trúc dữ liệu nội bộ tăng, điều này có thể hơi tốn thời gian.
IdentityHashMap​(Map<? extends K,​? extends V> m)
Tạo đối tượng IdentityHashMap với các ánh xạ copy từ một Map được chỉ định.

2- IdentityHashMap làm việc thế nào?

Cũng giống như HashMap, các nhà thiết kế Java đã sử dụng kỹ thuật băm (hashing technique) cho lớp IdentityHashMap để nâng cao hiệu suất truy cập và lưu trữ dữ liệu, và bây giờ chúng ta sẽ xem kỹ thuật này được sử dụng thế nào trong IdentityHashMap. Về cơ bản chúng ta phân tích xem điều gì sẽ xẩy ra khi gọi các phương thức IdentityHashMap.put(K,V), IdentityHashMap.get(K)IdentityHashMap.remove(key).
IdentityHashMap quản lý một mảng các đối tượng (Object[] table), mảng này có thể tự động tăng kích thước khi cần thiết. Và các cặp (key,value) được lưu trữ tại các vị trí (idx,idx+1).
Độ dài của mảng nội bộ được tính dựa trên kích thước trông đợi tối đa của IdentityHashMap giống như ví dụ dưới đây:
InternalArrayLength_test.java
package org.o7planning.identityhashmap.ex;

public class InternalArrayLength_test {

    private static final int MINIMUM_CAPACITY = 4;

    private static final int MAXIMUM_CAPACITY = 1 << 29;

    private static int capacity(int expectedMaxSize) {
        // assert expectedMaxSize >= 0;
        return (expectedMaxSize > MAXIMUM_CAPACITY / 3) ? MAXIMUM_CAPACITY
                : (expectedMaxSize <= 2 * MINIMUM_CAPACITY / 3) ? MINIMUM_CAPACITY
                        : Integer.highestOneBit(expectedMaxSize + (expectedMaxSize << 1));
    }

    public static void main(String[] args) {
        for (int i = 1; i < 15; i++) {
            int mapSize = i * 25;

            int arrayLength = 2 * capacity(mapSize);
            System.out.printf("Map size: %3d --> Internal Array length: %d%n",mapSize, arrayLength);
        }
    }
}
Output:
Map size:  25 --> Internal Array length: 128
Map size:  50 --> Internal Array length: 256
Map size:  75 --> Internal Array length: 256
Map size: 100 --> Internal Array length: 512
Map size: 125 --> Internal Array length: 512
Map size: 150 --> Internal Array length: 512
Map size: 175 --> Internal Array length: 1024
Map size: 200 --> Internal Array length: 1024
Map size: 225 --> Internal Array length: 1024
Map size: 250 --> Internal Array length: 1024
Map size: 275 --> Internal Array length: 1024
Map size: 300 --> Internal Array length: 1024
Map size: 325 --> Internal Array length: 1024
Map size: 350 --> Internal Array length: 2048

IdentityHashMap.put(key,value):

Khi phương thức IdentityHashMap.put(key,value) được gọi, IdentityHashMap sẽ tính toán vị trí dự kiến để lưu trữ cặp (notNullKey,value) trên mảng nội bộ theo công thức sau:
private static int hash(Object x, int length) {
    int h = System.identityHashCode(x);
    // Multiply by -127, and left-shift to use least bit as part of hash
    return ((h << 1) - (h << 8)) & (length - 1);
}
// Return default not null Object if key is null.
private static Object maskNull(Object key) {
    return (key == null ? NULL_KEY : key);
}

final Object notNullKey = maskNull(key);
int len = table.length; // Length of Object[] table.
int idx = hash(notNullKey, len);
Cặp (notNullKey,value) theo dự kiến sẽ được lưu trữ tại vị trí (idx,idx+1) của mảng. (Với idx được tính theo công thức trên).
  • Nếu table[idx]null thì cặp (notNullKey,value) sẽ được lưu trữ tại ví trí (idx,idx+1) của mảng.
  • Ngược lại nếu table[idx]==notNullKeytrue thì value sẽ được gán cho table[idx+1].
  • Ngược lại, ánh xạ (notNullKey,value) sẽ được lưu trữ tại vị trí (idx+2,idx+3), hoặc (idx+4,idx+5),....

IdentityHashMap.get(key):

Khi phương thức IdentityHashMap.get(key) được gọi, IdentityHashMap sẽ tính toán vị trí dự kiến tìm thấy ánh xạ với khoá notNullKey trên mảng nội bộ theo công thức tương tự:
private static int hash(Object x, int length) {
    int h = System.identityHashCode(x);
    // Multiply by -127, and left-shift to use least bit as part of hash
    return ((h << 1) - (h << 8)) & (length - 1);
}
// Return default not null Object if key is null.
private static Object maskNull(Object key) {
    return (key == null ? NULL_KEY : key);
}

final Object notNullKey = maskNull(key);
int len = table.length; // Length of Object[] table.
int idx = hash(notNullKey, len);
Ánh xạ với khoá notNullKey theo dự kiến sẽ được tìm thấy tại chỉ số idx của mảng. IdentityHashMap sử dụng toán tử == để so sánh notNullKeytable[idx].
// true or false?
notNullKey == table[idx]
Nếu notNullKey == table[idx]true thì phương thức sẽ trả về table[idx+1]. Ngược lại, notNullKey sẽ được so sánh với các phần tử tiếp theo tại các chỉ số idx+2, idx+4,... cho tới khi tìm thấy một chỉ số phù hợp hoặc tiến tới cuối của mảng. Nếu không tìm thấy phương thức sẽ trả về null.

IdentityHashMap.remove(key):

Phương thức IdentityHashMap.remove(key) cũng hoạt động gần tương tự như IdentityHashMap.get(key). Nếu tìm thấy vị trí (index,index+1) của ánh xạ cần loại bỏ, chúng sẽ được cập nhập thành null.
table[index] = null;
table[index+1] = null;

Kết luận:

IdentityHashMap sử dụng phương thức tĩnh System.identityHashCode(key) để tính toán hashcode của khoá. Về cơ bản phương thức này trả về một số nguyên rất hiếm khi trùng lặp. Kỹ thuật được sử dụng trong IdentityHashMap giúp nâng cao hiệu suất truy cập và lưu trữ dữ liệu. Giảm việc sử dụng toán tử == để so sánh các đối tượng.
Xem thêm Kỹ thuật băm (hashing technique) sử dụng trong HashMap:

3- Examples

IdentityHashMapEx1.java
package org.o7planning.identityhashmap.ex;

import java.util.IdentityHashMap;

public class IdentityHashMapEx1 {

    public static void main(String[] args) {
        String key1 = "Tom";
        String key2 = new String("Tom");
        
        // key1 == key2 ? false
        System.out.println("key1 == key2 ? " + (key1== key2)); // false

        IdentityHashMap<String, String> map = new IdentityHashMap<String, String>();
        
        map.put(key1, "Value 1");
        map.put(key2, "Value 2");
        
        System.out.println("Map Size: " + map.size());
        
        System.out.println(map);
    }  
} 
Output:
key1 == key2 ? false
Size: 2
{Tom=Value 1, Tom=Value 2}
Về cơ bản tất cả các tính năng của IdentityHashMap đều tuân thủ theo đặc tả của interface Map, ngoại trừ việc nó sử dụng toán tử == để so sánh các khoá, điều này đã vi phạm một chút so với đặc tả của interface Map (Đòi hỏi sử dụng phương thức equals để so sánh các khoá).
Xem thêm các ví dụ khác:

Xem thêm các chuyên mục:

Có thể bạn quan tâm

Đây là các khóa học trực tuyến bên ngoài website o7planning mà chúng tôi giới thiệu, nó có thể bao gồm các khóa học miễn phí hoặc giảm giá.