Cách sắp xếp được danh sách kiểu Map, Set, List?

anon21816065 · September 28, 2019, 3:38am

Hi there, cho mình hỏi danh sách kiểu HashMap, TreeMap, HashSet, TreeSet, LinkedList … có dùng được các thuật toán sắp xếp bubble Sort, Merge Sort, Quick Sort, Selection Sort, … không và sắp xếp như thế nào ? cảm ơn

Sherly1001 · September 28, 2019, 4:07am

Nếu muốn thì vẫn làm được.

Chỉ cần xây một methode swap() rồi áp dụng như bình thường.

Nhưng do các danh sách kiểu này muốn truy cập vào một phần tử bất kỳ khá phức tạp nên ít ai đi sort mấy cái này.

tntxtnt · September 28, 2019, 4:25am

sort để làm gì?

mấy cái ctdl đó dùng cho việc X, em đi lấy nó làm việc Y sao hợp lý? Ví dụ lấy cây búa đi cưa gỗ :V :V :V

anon21816065 · September 28, 2019, 4:55am

ví dụ như mình có 1 cái hashMap là từ điển Anh-Việt với key là từ tiếng anh tương ứng với value là nghĩa tiếng việt khi đó em muốn sắp xếp theo thứ tự chữ cái thì không được ạ ? VD : danh sách nhân viên với key là mã số nhân viên ( ai vào trước thì số nhỏ, vào sau số lớn ) còn value là object nhân viên thì sao ạ

rogp10 · September 28, 2019, 5:06am

HashMap thì cần gì sắp xếp nữa bạn
HashSet TreeSet cũng tự nó sắp xếp rồi.

hungaya · September 28, 2019, 4:00pm

Cái sort() của Java nó chạy trên interface List mà, nên cái gì liên quan đến list nó chơi hết, từ ArrayList, LinkedList,… . Còn Map này nọ nó không implement List nên nó không chơi đâu (mà chơi cày cối cũng không được vì Map có tận 2 type params trong khi List có 1 type param)

Trong sort() có những gì, nói chung nó chia thành 2 loại: sort() cho mảng dạng int[], double[],… và sort() cho List. Mỗi sort dùng nhiều giải thuật sort khác nhau. Nếu số lượng phần tử nhỏ thì insertion sort, nếu lớn hơn chút dùng quick sort, merge sort, tim sort. 3 cái sort sau nó không chia mảng thành 2 phần mà nó chia từ 3 tới 6 phần, có những phần nó gọi code C sort cho nhanh nữa.

Túm lại sort của Java phức tạp (để chọc client là chính, còn performance là phụ ). Bạn có thể mở cái source code xem cho vui, nói trước là tác giả viết siêu xấu, đọc mà muốn chửi thề luôn.

tntxtnt · September 28, 2019, 12:18pm

em có thể xài TreeSet :V hoặc em có thể tạo 1 mảng key, sort mảng key lại, rồi truy cập key bằng binary search.

nếu em muốn gõ “th” mà nó hint the, their, v.v… thì em có thể tự viết ctdl trie (prefix tree) để duyệt:
https://www.programcreek.com/2014/05/leetcode-implement-trie-prefix-tree-java/

bathudaide · October 1, 2019, 9:15am

Map

HashMap: Lưu trữ ngẫu nhiên, không thể sắp xếp.
LinkedHashMap: Lưu trữ theo thứ tự chèn, có thể sắp xếp.
TreeMap: Tự động sắp xếp tăng dần theo key, có thể sắp xếp.

Set

HashSet: Lưu trữ ngẫu nhiên, không thể sắp xếp.
LinkedHashSet: Lưu trữ theo thứ tự chèn, có thể sắp xếp.
TreeSet: Tự động sắp xếp các phần tử tăng dần (hoặc giảm dần), có thể sắp xếp.

bathudaide · September 28, 2019, 3:38pm

Bạn chắc có chỗ nhầm lẫn, phương thức sort() bạn nói là thuộc class Collections chứ không phải thuộc interface Collection. Collections.sort() chỉ dùng cho List kiểu generic. Còn phương thức sort() dùng cho mảng int, double, … bạn nói là thuộc lớp Arrays.

hungaya · September 28, 2019, 3:59pm

Cám ơn bạn nhiều nha, thực sự mình chỉ đọc code 2 loại sort đó thôi.
Mà đính chính cái, sort() mình biết là static method rồi, nên mình ghi là “chạy trên” chứ không có “thuộc” gì cả.

anon21816065 · October 1, 2019, 3:48am

cảm ơn anh ! nhưng sao em test hashMap với hashSet cũng tự sắp xếp tăng dần ạ ?

import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedHashMap;
import java.util.LinkedHashSet;
import java.util.TreeMap;
import java.util.TreeSet;

public class DayNhauHoc {
	public static void main(String[] args) {

		HashMap<Integer, Double> hashmap = new HashMap();
		TreeMap<Integer, Double> treemap = new TreeMap();
		LinkedHashMap<Integer, Double> linkedHashMap = new LinkedHashMap();

		HashSet<Integer> hashSet = new HashSet();
		TreeSet<Integer> treeSet = new TreeSet();
		LinkedHashSet<Integer> linkedHashSet = new LinkedHashSet();

		hashmap.put(8, 88.0);
		hashmap.put(3, 88.0);
		hashmap.put(9, 99.0);
		hashmap.put(1, 11.0);
		hashmap.put(5, 55.0);
		hashmap.put(1, 11.0);
		hashmap.put(1, 11.0);
		hashmap.put(1, 11.0);
		hashmap.put(1, 11.0);
		hashmap.remove(3);

		treemap.put(8, 88.0);
		treemap.put(3, 88.0);
		treemap.put(9, 99.0);
		treemap.put(1, 11.0);
		treemap.put(5, 55.0);
		treemap.put(1, 11.0);
		treemap.put(1, 11.0);
		treemap.put(1, 11.0);
		treemap.put(1, 11.0);
		treemap.remove(3);

		linkedHashMap.put(8, 88.0);
		linkedHashMap.put(3, 88.0);
		linkedHashMap.put(9, 99.0);
		linkedHashMap.put(1, 11.0);
		linkedHashMap.put(5, 55.0);
		linkedHashMap.put(1, 11.0);
		linkedHashMap.put(1, 11.0);
		linkedHashMap.put(1, 11.0);
		linkedHashMap.put(1, 11.0);
		linkedHashMap.remove(3);

		hashSet.add(8);
		hashSet.add(9);
		hashSet.add(1);
		hashSet.add(5);
		hashSet.add(1);
		hashSet.add(1);
		hashSet.add(1);
		hashSet.add(1);
		hashSet.remove(3);

		treeSet.add(8);
		treeSet.add(9);
		treeSet.add(1);
		treeSet.add(5);
		treeSet.add(1);
		treeSet.add(1);
		treeSet.add(1);
		treeSet.add(1);
		treeSet.remove(3);

		linkedHashSet.add(8);
		linkedHashSet.add(9);
		linkedHashSet.add(1);
		linkedHashSet.add(5);
		linkedHashSet.add(1);
		linkedHashSet.add(1);
		linkedHashSet.add(1);
		linkedHashSet.add(1);
		linkedHashSet.remove(3);

		System.out.println("hashMap");
		System.out.println(hashmap);
		System.out.println("treeMap");
		System.out.println(treemap);
		System.out.println("LinkedhashMap");
		System.out.println(linkedHashMap);
		System.out.println("hashSet");
		System.out.println(hashSet);
		System.out.println("TreeSet");
		System.out.println(treeSet);
		System.out.println("LinkedHashSet");
		System.out.println(linkedHashSet);
	}
}

Kết quả Console :

hashMap
{1=11.0, 5=55.0, 8=88.0, 9=99.0}
treeMap
{1=11.0, 5=55.0, 8=88.0, 9=99.0}
LinkedhashMap
{8=88.0, 9=99.0, 1=11.0, 5=55.0}
hashSet
[1, 5, 8, 9]
TreeSet
[1, 5, 8, 9]
LinkedHashSet
[8, 9, 1, 5]

bathudaide · October 1, 2019, 1:45pm

Bạn xem document của HashMap trên trang chủ của Oracle

This class makes no guarantees as to the order of the map; in particular, it does not guarantee that the order will remain constant over time.

Đoạn code dưới đây mình sẽ tạo một HashMap với key là string và value là độ dài của string đó

public static void init() {
	List<String> list = Arrays.asList("public", "static", "void", "main");
	HashMap<String, Integer> map = new HashMap<>();
	// Map<String, Integer> map = new TreeMap<>();
	for (int i = 0; i < 9; i++) {
		list.forEach(s -> map.put(s, s.length()));
		System.out.println(map);
		map.clear();
		Collections.shuffle(list);
	}
}

Nếu HashMap tự động sắp xếp các phần tử (theo tiêu chí nào đó) thì kết quả sẽ ra 9 dòng giống nhau nhưng đây là kết quả từ console của mình

{static=6, void=4, public=6, main=4}
{static=6, void=4, public=6, main=4}
{void=4, static=6, public=6, main=4}
{void=4, static=6, public=6, main=4}
{void=4, static=6, public=6, main=4}
{static=6, void=4, public=6, main=4}
{void=4, static=6, public=6, main=4}
{void=4, static=6, public=6, main=4}
{static=6, void=4, public=6, main=4}

Còn đây là là kết quả dùng TreeMap

{main=4, public=6, static=6, void=4}
{main=4, public=6, static=6, void=4}
{main=4, public=6, static=6, void=4}
{main=4, public=6, static=6, void=4}
{main=4, public=6, static=6, void=4}
{main=4, public=6, static=6, void=4}
{main=4, public=6, static=6, void=4}
{main=4, public=6, static=6, void=4}
{main=4, public=6, static=6, void=4}