Khóa tổng hợp: Hướng dẫn cách xử lý chúng

Khóa tổng hợp là khi cần có sự kết hợp của dữ liệu để xác định “khóa” cho việc tra cứu bản đồ hoặc bộ đệm của bạn. Một ví dụ về điều này có thể là khi bạn cần lưu các giá trị vào bộ nhớ đệm dựa trên tên khách hàng cũng như vai trò của người dùng. Trong trường hợp như thế này, bộ đệm của bạn cần có khả năng lưu trữ các giá trị duy nhất dựa trên từng tiêu chí trong số hai (hoặc nhiều) tiêu chí này.

Có một số cách khác nhau để xử lý khóa tổng hợp trong mã.

Kết hợp các tiêu chí thành một chuỗi

Câu trả lời đầu tiên được nhiều người quan tâm nhất là kết hợp các tiêu chí thành một chuỗi để sử dụng làm khóa. Thật đơn giản và không tốn nhiều công sức:

 private String getMapKey(Long userId, String userLocale) { return userId + "." userLocale; }

Đây là một cách khá cơ bản để xử lý vấn đề. Việc sử dụng khóa chuỗi có thể giúp việc gỡ lỗi và điều tra dễ dàng hơn vì khóa bộ đệm có định dạng mà con người có thể đọc được. Nhưng có một số vấn đề cần lưu ý với cách tiếp cận này:

1. Nó yêu cầu tạo một chuỗi mới trên mỗi lần tương tác với bản đồ. Mặc dù việc phân bổ chuỗi này thường nhỏ nhưng nếu bản đồ được truy cập thường xuyên, nó có thể dẫn đến một số lượng lớn các lần phân bổ, gây mất thời gian và cần được thu gom rác. Kích thước của phân bổ chuỗi cũng có thể lớn hơn tùy thuộc vào mức độ lớn của các thành phần khóa hoặc số lượng bạn có.

   
   

2. Bạn cần đảm bảo rằng khóa tổng hợp bạn tạo không thể bị giả mạo thành một giá trị khóa khác:

 public String getMapKey(Integer groupId, Integer accessType) { return groupId.toString() + accessType.toString(); }

Ở phần trên, nếu bạn có groupId = 1 và accessType = 23, thì đó sẽ là khóa bộ đệm giống như groupId = 12 và accessType = 3. Bằng cách thêm ký tự phân tách giữa các chuỗi, bạn có thể ngăn chặn kiểu chồng chéo này. Nhưng hãy cẩn thận về các phần tùy chọn của khóa:

 public String getMapKey(String userProvidedString, String extensionName) { return userProvidedString + (extensionName == null ? "" : ("." + extensionName)); }

Trong ví dụ trên, ExtensionName là một phần tùy chọn của khóa. Nếu tên tiện ích mở rộng là tùy chọn, userProvidedString có thể bao gồm dấu phân cách và Tên tiện ích mở rộng hợp lệ, đồng thời có quyền truy cập vào dữ liệu bộ đệm mà lẽ ra nó không có quyền truy cập.

Khi sử dụng chuỗi, bạn sẽ muốn nghĩ đến cách kết hợp dữ liệu của mình để tránh bất kỳ xung đột nào trong các phím. Đặc biệt là xung quanh bất kỳ đầu vào nào do người dùng tạo cho khóa.

Sử dụng Bản đồ/Bộ đệm lồng nhau

Một tùy chọn khác là hoàn toàn không kết hợp các khóa và thay vào đó, lồng các cấu trúc dữ liệu của bạn (Bản đồ Bản đồ Bản đồ):

 Map<Integer, Map<String, String>> groupAndLocaleMap = new HashMap<>(); groupAndLocaleMap.computeIfAbsent(userId, k -> new HashMap()).put(userLocale, mapValue);

Điều này có ưu điểm là không cần phân bổ bất kỳ bộ nhớ mới nào khi tương tác với bản đồ vì các giá trị truyền vào cho các khóa đã được phân bổ. Và mặc dù bạn cần thực hiện nhiều lần tra cứu để có được giá trị cuối cùng, nhưng bản đồ sẽ nhỏ hơn.

Nhưng nhược điểm của phương pháp này là càng đi sâu vào tổ thì càng phức tạp. Ngay cả khi chỉ có hai cấp độ, việc khởi tạo bản đồ có thể trông khó hiểu. Khi bạn bắt đầu xử lý 3 phần dữ liệu trở lên, điều này có thể khiến mã của bạn trở nên rất dài dòng. Trên hết, mỗi cấp độ đều yêu cầu kiểm tra null để tránh con trỏ null.

Một số “bộ phận chính” cũng có thể không hoạt động tốt như khóa bản đồ. Mảng hoặc bộ sưu tập không có phương thức mặc định bằng để so sánh nội dung của chúng. Vì vậy, bạn sẽ cần phải triển khai chúng hoặc sử dụng giải pháp thay thế khác.

Việc sử dụng bản đồ lồng nhau cũng có thể trở nên kém hiệu quả về mặt không gian hơn tùy thuộc vào mức độ độc đáo của từng cấp độ khóa của bạn.

Tạo một đối tượng khóa tổng hợp

Tùy chọn cuối cùng là thay vì kết hợp các giá trị khóa thành một chuỗi, hãy tạo một đối tượng tùy chỉnh cho khóa:

 private class MapKey { private final int userId; private final String userLocale; public MapKey(int userId, String userLocale) { this.userId = userId; this.userLocale = userLocale; } @Override public boolean equals(Object o) { if (this == o) return true; if (o == null || getClass() != o.getClass()) return false; MapKey mapKey = (MapKey) o; return userId == mapKey.userId && Objects.equals(userLocale, mapKey.userLocale); } @Override public int hashCode() { return Objects.hash(userId, userLocale); } }

Trong khi mọi tương tác vẫn yêu cầu cấp phát bộ nhớ mới cho một đối tượng mới. Việc phân bổ khóa đối tượng nhỏ hơn đáng kể so với phân bổ khóa cần thiết cho một chuỗi tổng hợp. Lý do cho điều này là các phần tạo nên khóa không cần phải phân bổ lại dưới dạng chuỗi. Thay vào đó, chỉ có khóa đối tượng gói yêu cầu bộ nhớ mới.

Đối tượng khóa tổng hợp cũng có thể cho phép tùy chỉnh trong việc triển khai mã băm và đẳng thức khóa. Chẳng hạn như bỏ qua cách viết hoa trong chuỗi hoặc sử dụng mảng hoặc tập hợp làm một phần của khóa.

Tuy nhiên, nhược điểm ở đây là nó yêu cầu nhiều mã hơn so với chuỗi tổng hợp. Và nó yêu cầu đảm bảo bạn có các hợp đồng bằng và mã băm hợp lệ trong lớp khóa cho bản đồ của bạn.

Vậy tôi nên chọn cái nào?

Nói chung, tôi khuyên bạn nên sử dụng khóa chuỗi tổng hợp. Nó đơn giản và dễ hiểu, yêu cầu ít mã nhất và dễ gỡ lỗi nhất sau này. Mặc dù nó có thể hoạt động chậm nhất, nhưng việc viết mã đơn giản, dễ đọc thường quan trọng hơn những lợi ích bạn sẽ nhận được khi sử dụng một trong hai tùy chọn còn lại. Nhớ:

“Tối ưu hóa sớm là gốc rễ của mọi tội lỗi” Donald Knuth

Nếu bạn không có bằng chứng hoặc lý do để tin rằng việc tra cứu bản đồ/bộ đệm của bạn sẽ gây tắc nghẽn hiệu suất, hãy sử dụng tính năng dễ đọc.

Nhưng nếu bạn ĐANG ở trong trường hợp thông lượng tới bản đồ hoặc bộ đệm của bạn rất cao thì bạn nên chuyển sang một trong hai tùy chọn còn lại. Chúng ta hãy xem cả 3 so sánh với nhau như thế nào về hiệu suất cũng như kích thước phân bổ bộ nhớ của chúng.

Để kiểm tra 3 tình huống trên, tôi đã viết mã sao chép cách triển khai giống nhau của cả 3 tình huống cho một khóa tổng hợp. Bản thân khóa bao gồm một giá trị số nguyên, một giá trị chuỗi và một giá trị dài. Tất cả ba cách triển khai đều sử dụng cùng một dữ liệu thử nghiệm trong mỗi lần chạy để tạo khóa.

Tất cả các lần chạy đều được thực thi với 1 triệu bản ghi trên bản đồ (hashmap của Java đã được sử dụng). 3 lần chạy đã được thực hiện để xây dựng khóa với các kết hợp kích thước khóa khác nhau:

• 100 int, 100 chuỗi, 100 long - 1 triệu khóa duy nhất

• 1 int, 1 chuỗi, 1.000.000 độ dài— 1 triệu khóa duy nhất

• 1.000.000 int, 1 chuỗi, 1 dài - 1 triệu khóa duy nhất

  
  

Đầu tiên, chúng ta hãy xem mỗi bản đồ chiếm bao nhiêu dung lượng trong heap. Điều này rất quan trọng vì nó ảnh hưởng đến lượng bộ nhớ cần thiết để chạy ứng dụng của bạn.

Có một lưu ý rõ ràng thú vị cần thực hiện ở đây: trong kịch bản cuối cùng (1.000.000 int), kích thước bản đồ lồng nhau lớn hơn đáng kể so với các bản đồ khác. Điều này là do trong trường hợp này, các bản đồ lồng nhau tạo ra 1 bản đồ cấp một với 1 triệu mục nhập. Sau đó, ở cấp độ thứ hai và thứ ba, nó tạo ra 1 triệu bản đồ chỉ với một mục nhập.

Tất cả những bản đồ lồng nhau đó đều lưu trữ thêm chi phí và hầu hết đều trống. Đây rõ ràng là một trường hợp khó khăn, nhưng tôi muốn chứng minh điều đó để đưa ra quan điểm. Khi sử dụng triển khai bản đồ tổ, tính duy nhất (và thứ tự của tính duy nhất đó) rất quan trọng.

Nếu bạn đảo ngược thứ tự thành 1, 1, 1 triệu, bạn thực sự nhận được yêu cầu lưu trữ thấp nhất.

Trong hai trường hợp còn lại, ánh xạ lồng nhau là hiệu quả nhất, với đối tượng khóa tùy chỉnh ở vị trí thứ hai và các khóa chuỗi ở vị trí cuối cùng.

Tiếp theo, hãy xem thời gian cần thiết để tạo từng bản đồ này từ đầu:

Một lần nữa, chúng ta thấy các bản đồ lồng nhau hoạt động kém nhất trong kịch bản 1 triệu-1–1 về phân bổ bộ nhớ, nhưng ngay cả khi đó, nó vẫn vượt trội so với các bản đồ khác về thời gian CPU. Ở phần trên, chúng ta cũng có thể thấy khóa Chuỗi hoạt động kém nhất trong mọi trường hợp trong khi việc sử dụng đối tượng khóa tùy chỉnh chậm hơn một chút và yêu cầu phân bổ nhiều bộ nhớ hơn so với các khóa lồng nhau.

Cuối cùng, hãy xem xét trường hợp thông lượng cao nhất và mức độ hiệu quả của việc đọc. Chúng tôi đã thực hiện 1 triệu thao tác đọc (1 thao tác cho mỗi khóa được tạo); chúng tôi không bao gồm bất kỳ khóa không tồn tại nào.

Đây là lúc chúng ta thực sự thấy việc tra cứu khóa dựa trên chuỗi chậm đến mức nào. Cho đến nay, đây là tùy chọn chậm nhất và phân bổ nhiều bộ nhớ nhất trong số 3 tùy chọn. Đối tượng khóa tùy chỉnh thực hiện “gần” với việc triển khai bản đồ lồng nhau nhưng vẫn chậm hơn một chút.

Tuy nhiên, trong quá trình phân bổ bộ nhớ tra cứu, hãy chú ý xem các bản đồ lồng nhau hoạt động tốt như thế nào. Không, đó không phải là trục trặc trong biểu đồ; tra cứu một giá trị trong các bản đồ lồng nhau không yêu cầu phân bổ thêm bộ nhớ để thực hiện tra cứu. Làm sao điều đó có thể được?

Chà, khi kết hợp các đối tượng tổng hợp thành một khóa chuỗi, bạn cần cấp phát bộ nhớ cho một đối tượng chuỗi mới mỗi lần:

 private String lookup(int key1, String key2, long key3) { return map.get(key1 + "." + key2 + "." + key3); }

Khi sử dụng khóa tổng hợp, bạn vẫn cần cấp phát bộ nhớ cho đối tượng khóa mới. Nhưng vì các thành viên của đối tượng đó đã được tạo và tham chiếu nên nó vẫn phân bổ ít hơn nhiều so với một chuỗi mới:

 private String lookup(int key1, String key2, long key3) { return map.get(new MapKey(key1, key2, key3)); }

Tuy nhiên, việc triển khai bản đồ lồng nhau không yêu cầu cấp phát bộ nhớ mới khi tra cứu. Bạn đang sử dụng lại các phần đã cho làm chìa khóa cho từng bản đồ lồng nhau:

 private String lookup(int key1, String key2, long key3) { return map.get(key1).get(key2).get(key3); }

Vì vậy, dựa trên những điều trên, cái nào hiệu quả nhất?

Dễ dàng nhận thấy rằng các bản đồ lồng nhau có hiệu quả cao nhất trong hầu hết các trường hợp. Nếu bạn đang tìm kiếm hiệu suất thô trong hầu hết các trường hợp sử dụng thì đó có thể là lựa chọn tốt nhất. Tuy nhiên, bạn nên thực hiện thử nghiệm của riêng mình để xác nhận trường hợp sử dụng của mình.

Đối tượng chính tạo ra một tùy chọn có mục đích chung rất tốt khi các bản đồ lồng nhau trở nên không thực tế hoặc không thể sử dụng để triển khai. Và khóa chuỗi tổng hợp, mặc dù dễ thực hiện nhất nhưng hầu như luôn chậm nhất.

Điểm cuối cùng cần cân nhắc khi tìm cách triển khai khóa tổng hợp là bạn có thể kết hợp những điều trên. Ví dụ: bạn có thể sử dụng các bản đồ lồng nhau cho một hoặc hai cấp độ đầu tiên, sau đó sử dụng đối tượng khóa tổng hợp để đơn giản hóa các cấp độ sâu hơn.

Điều này vẫn có thể giữ cho dữ liệu của bạn được phân vùng để tra cứu nhanh trong khi vẫn tối ưu hóa hiệu suất lưu trữ và tra cứu. Và giữ cho mã của bạn có thể đọc được.

TLDR;

Hầu hết thời gian, chỉ cần giữ nó đơn giản. Kết hợp các khóa tổng hợp của bạn thành một khóa chuỗi để lưu trữ trong bản đồ hoặc bộ đệm nếu đó là tùy chọn dễ dàng nhất và hiệu suất không phải là mối quan tâm lớn.

Trong các trường hợp mà hiệu suất là quan trọng, hãy đảm bảo thực hiện thử nghiệm của riêng bạn. Nhưng sử dụng bản đồ lồng nhau sẽ mang lại hiệu quả cao nhất trong hầu hết các trường hợp. Nó cũng có thể sẽ có yêu cầu lưu trữ nhỏ nhất. Và các khóa tổng hợp vẫn là một giải pháp thay thế hiệu quả khi việc ánh xạ lồng nhau trở nên không thực tế.

Cũng được xuất bản ở đây