Trang 1 trên tổng số 2 12 Cuối cùngCuối cùng
Từ 1 tới 10 trên tổng số 11 kết quả

Đề tài: Lập trình tìm kiếm | Tìm kiếm với mảng băm (hashtable): ý tưởng & cài đặt

  1. #1
    Ngày gia nhập
    05 2007
    Nơi ở
    HCMC
    Bài viết
    60

    Mặc định Lập trình tìm kiếm | Tìm kiếm với mảng băm (hashtable): ý tưởng & cài đặt

    Thấy anh em sôi nổi quá, sonhn mỗ cũng tham gia 1 bài CTDL cho phong phú diễn đàn. Tuy hashtable có sẵn trong VC++ rồi, nhưng tìm hiểu và xây dựng nó cũng là cách rèn luyện tay nghề.

    Hashing là cái gì?

    Hashing (mảng băm) là một cấu trúc dữ liệu cho phép lưu trữ & tìm kiếm giá trị (dạng chuỗi ký tự) ở độ phức tạp O(1). Nghĩa là tốc độ tìm kiếm phần tử luôn là một hằng số, dù số phần tử lên đến cả tỷ.

    Làm sao được như vậy?

    Ví dụ: muốn tổ chức một mảng để lưu trữ 3 chuỗi "dream", "pete", và "soda". Trước hết, khởi tạo một mảng như bình thường, với mỗi phần tử kiểu chuỗi. Sau đó, mình lấy 3 chuỗi trên và tính giá trị hashcode cho chúng theo cách sau: qui ước ký tự 'a'=1, 'b'=2,... đến 'z'=26. Ta có:

    Code:
    dream = 4 + 18 + 5 + 1 + 13 = 41
    pete = 16 + 5 + 20 + 5 = 46
    soda = 19 + 15 + 4 + 1 = 39
    Tính xong rồi, thế là đặt "dream" vào vị trí 41, "pete" vào vị trí 46, và "soda" vào vị trí 39 của mảng. Sau này, muốn truy xuất, thì mình tính hashcode 1 lần nữa rồi vô mảng mà lấy.

    Sao đơn giản dzậy?

    Thực tế thì phức tạp hơn 1 chút. Cách làm như ví dụ trên tệ ở chỗ: chỉ để chứa 3 phần tử mà cần 1 cái mảng tới 46 "ô". Thế thì giải quyết như thế này: lấy hashcode thu được rồi chia modulo cho tổng sức chứa. Ví dụ, nếu chỉ muốn chứa 10 phần tử, ta tính như vầy:

    Code:
    dream = 41 % 10 = 1
    pete = 46 % 10 = 6
    soda = 39 % 10 = 9
    Thế thì đặt "dream" vô vị trí 1, "pete" vô 6, và "sodo" vô 9. Xem chừng ổn 1 chút.

    Hết rồi hả?

    Chưa đâu! xem thử trường hợp này nè: tui muốn bổ sung thêm vào mảng trên 1 phần tử nữa, là "sado". Tính hashcode cho phần tử mới:
    Code:
    "sado" = 19 + 1 + 4 + 15 = 39, lấy 39 % 10 = 9
    Anh chàng "sado" này bị trùng chổ với tiểu thư "soda" rồi!

    Vậy giải quyết làm sao?

    Phối hợp cả 2 cách bên dưới:

    - Thứ nhất: thiết kế một hàm băm (hash funtion) thật tốt. Phải "băm" làm sao cho tỷ lệ trùng nhau giữa các chuỗi khác nhau là rất thấp. Ví dụ: đem nhân giá trị của ký tự cho 1 số nào đó, cộng hết lại, rồi chia modulo cho 1 số nguyên tố (vì sao lại là nguyên tố? thử suy nghĩ nhé!)

    - Thứ hai: nếu đã băm rồi mà vẫn còn đụng độ thì dùng một trong 2 kỹ thuật linear-probing và buckets để giải quyết:

    + Linear-probing: ý tưởng là dò tìm vị trí trống tiếp theo rồi chèn phần tử bị đụng độ vào đó. Trong ví dụ trên, khi anh "sado" bị đụng tại vị trí 9, tôi tìm và thấy ô thứ 10 còn trống, thế thì tôi chèn "anh" vào đó. Khi mảng đầy, tôi resize lại mảng cho lớn hơn 1 chút.

    + Buckets: Thay vì cố gắng tìm trong danh sách một vị trí còn trống kế tiếp, kỹ thuật buckets tổ chức lại cấu trúc danh sách để có thể đặt nhiều phần tử vào cùng một vị trí, như thế này:
    Code:
    0|
    1|-"dream"
    2|
    3|
    4|
    5|
    6|-"pete"
    7|
    8|
    9|-"soda" -- "sado"
    Ở đây, ta tổ chức một danh sách liên kết 2 chiều. Khi bị đụng, ta nối phần tử mới vào phía sau phần tử đã có.

    Làm gì thì làm, thực tế đụng độ vẫn có thể xảy ra. Khi có nhiều phần tử được đặt cùng một vị trí thì tốc độ tìm kiếm sẽ bị giảm xuống. Người ra đề xuất giải pháp thay đổi lại kích thước của danh sách để các phần tử được phân phối một cách thích hợp. Thông thường người ta dựa vào một giá trị gọi là thừa số tải (load factor) – tỷ lệ giữa số phần tử đã được lưu trữ trên tổng số phần tử của danh sách. Khi tỷ lệ này chạm đến mức thừa số tải thì thao tác thay đổi kích thước tự động được thi hành. Trong ví dụ trên, thừa số tải là 4 / 10 = 40%. Thông thường một thừa số tải thích hợp là 0.75, tức 75%.

    Code ví dụ đi!

    Ờ, có chương trình nhỏ (viết cách đây 2 năm) đây nè, viết bằng Visual C++, sử dụng kỹ thuật buckets. Mỗi phần tử là một kiểu cấu trúc gồm 3 phần:
    -Khóa (key): kiểu chuỗi ký tự
    -Giá trị (value): kiểu số nguyên
    -Con trỏ đến phần tử kế tiếp (next)

    Code:
    #include <stdio.h>
    #include <tchar.h>
    #include <windows.h>
    
    const long PARALEN = 100;	//số lượng trung bình các phần tử thực tế
    
    class Hashtable
    {
    private:
    	struct ItemType{
    		TCHAR key[50];
    		long value;
    		ItemType *next;
    	};
    
    	typedef ItemType *Item;
    
    	Item *data;	//data là một danh sách các Item
    	long capacity;	//sức chứa của Hashtable
    	long num;	//num là số lượng các phần tử thực tế
    
    	//Hàm làm tròn dung lượng hashtable
    	long GetRoundCapacity()
    	{
    		long result = 1;
    
    		while (result < capacity)
    		{
    			result*=10;
    		}
    		return result;
    	}
    
    	//Hàm lấy mã băm 
    	long GetHashCode(const TCHAR *string)
    	{
    		long code = 0;
    		long sum = 0;
    		long round = GetRoundCapacity();
    		char length = _tcslen(string);
    
    		for(char i=0; i < length; i++)
    			sum = sum*3 + string[i];
    
    		while (sum > 0)
    		{
    			code = code + sum%round;
    			sum = sum/round;
    		}
    		return code%capacity;
    	}
    
    public:
    	//Hàm dựng
    	Hashtable(long capac)
    	{
    		capacity = capac;
    		data = (Item *)malloc(capacity*sizeof(Item));
    		num = 0;
    		for(long i=0; i<capacity; i++)
    		{	
    			data[i] = NULL;
    		}
    	}
    
    	//Kiểm tra một khóa có tồn tại trong hashtable hay không 
    	BOOL Contain(const TCHAR *key)
    	{
    		Item temp;
    		BOOL found = FALSE;
    		long pos = GetHashCode(key);
    
    		temp = data[pos];
    		while ((temp != NULL) && (!found))
    		{
    			if (_tcsicmp(temp->key,key)==0)	
    				found = TRUE;
    			else
    				temp = temp->next;
    		}
    		return found;
    	}
    
    	//Chèn một phần tử vào hashtable 
    	BOOL Put(const TCHAR *key, const long value)
    	{
    		Item temp, current;
    		long pos = GetHashCode(key);
    
    		if (Contain(key)) return FALSE;	//nếu khóa đã tồn tại thì kết thúc
    
    		temp = (Item)malloc(sizeof(ItemType));	//tạo một phần tử mới
    		_tcscpy(temp->key, key);
    		temp->value = value;
    
    		temp->next = data[pos];	//chèn phần tử mới vào đầu
    		data[pos] = temp;
    
    		return TRUE;
    	}
    
    	//Phương thức lấy giá trị dựa vào khóa cho trước
    	long Get(const TCHAR *key)
    	{
    		long pos = GetHashCode(key);
    		Item temp = data[pos];
    		BOOL found = FALSE;
    
    		while ((temp != NULL) && (!found))
    		{
    			if (_tcsicmp(temp->key, key)==0)
    				found = TRUE;
    			else
    				temp = temp->next;
    		}
    
    		if (found)
    			return (temp->value);
    		else
    			return -1;
    	}
    
    	//Phương thức loại bỏ một phần tử ra khỏi hashtable 
    	void Remove(const TCHAR *key)
    	{
    		Item temp, temp2;
    		BOOL done = FALSE;
    		long pos = GetHashCode(key);
    		
    		if (data[pos]==NULL) return;	//nếu không tồn tại khóa thì kết thúc
    
    		temp = data[pos];
    		if (_tcsicmp(temp->key, key)==0)	//nếu khóa nằm ngay vị trí đầu thì loại bỏ phần tử đầu
    		{	
    			data[pos] = data[pos]->next;
    			free(temp);
    		}
    		else				//ngược lại, loại bỏ phần tử ở giữa nếu tìm thấy
    		{					
    			temp2 = temp->next;
    			while ((!done) && (temp2!=NULL))
    			{
    				if (_tcsicmp(temp2->key,key)==0)
    				{
    					temp->next = temp2->next;
    					free(temp2);
    					done = TRUE;
    				}
    				else{
    					temp = temp->next;
    					temp2 = temp2->next;
    				}
    			}
    	}}
    	
    	// In tất cả các phần tử trong hashtable
    	void ViewAll()
    	{
    		Item temp;
    
    		if (num <= 0)
    		{
    			printf("No Item");
    			return;
    		}
    
    		for(long i = 0; i < capacity; i++)
    		{
    			if (data[i]!= NULL)
    			{
    				temp = data[i];
    				while (temp != NULL)
    				{
    					printf("%s \t %d \n",temp->key, temp->value);
    					temp = temp->next;
    				}
    			}
    		}
    	}
    };
    
    //kiem tra xem thu
    void main()
    {
    	Hashtable T(20);
    
    	T.Put("vitung",30);
    	T.Put("tranduy",30);
    	T.Put("dinhtu",10);
    
    	T.ViewAll();
    }
    Đã được chỉnh sửa lần cuối bởi sonhn : 28-05-2007 lúc 06:38 PM.

  2. #2
    Ngày gia nhập
    09 2006
    Nơi ở
    /usr/share/.hack@
    Bài viết
    1,433

    #_Bài này tuyển đấy ...Để tạo một list các bài tuyển trong mục này mới được.
    None!

  3. #3
    Ngày gia nhập
    04 2007
    Bài viết
    128

    Bảng băm đóng : mỗi khóa ứng với một địa chỉ, thời gian truy xuất là hằng số
    Bảng băm mở : một số khóa có cùng địa chỉ, lúc này mỗi mục địa chỉ sẽ là một danh sách liên kết các phần tử có cùng địa chỉ, thời gian truy xuất có thể bị suy giảm đôi chút
    thế có so sánh được độ phức tạp của 2 cái này ko?
    Chú Sơn làm băm kép chưa? Post lên luôn nhá!!

  4. #4
    Ngày gia nhập
    01 2007
    Bài viết
    412

    Mình xin có chút ý kiến, nếu có sai mong bà con "khoan hồng độ lượng":
    Hashing (mảng băm) là một cấu trúc dữ liệu cho phép lưu trữ & tìm kiếm giá trị (dạng chuỗi ký tự) ở độ phức tạp O(1). Nghĩa là tốc độ tìm kiếm phần tử luôn là một hằng số, dù số phần tử lên đến cả tỷ.
    Ở trên, cậu nói hơi chung chung. Thật ra, chỉ có bảng băm đóng mới có độ phức tạp tìm kiếm là O(1) (tối thiểu = tối đa). Còn bảng băm mở thì độ phức tạp tối thiểu là O(1), và còn có thế lớn hơn khi bảng băm có nhiều sự đụng độ
    - Thứ nhất: thiết kế một hàm băm (hash funtion) thật tốt. Phải "băm" làm sao cho tỷ lệ trùng nhau giữa các chuỗi khác nhau là rất thấp. Ví dụ: đem nhân giá trị của ký tự cho 1 số nào đó, cộng hết lại, rồi chia modulo cho 1 số nguyên tố (vì sao lại là nguyên tố? thử suy nghĩ nhé!)
    Một số phương pháp xây dựng hàm băm:
    a.Hàm băm dạng bản tra
    Ví dụ: cho bảng chữ cái alphabet, chữ cái a được băm vào địa chỉ 0, chữ cái b được băm vào địa chỉ 1,..., của bảng băm
    b.Hàm băm sử dụng phương pháp chia:
    - Dùng số dư: h(k) = k % m
    k là khóa, m là kích thước bảng băm
    ==> vấn đề là chọn m làm sao đây??
    Nếu chọn m= pow(2,n) (2^n) thông thường không tốt vì h(k) = k mod pow(2,n) sẽ chọn cùng n bits thấp của k ==> nên chọn m là số nguyên tố gần với pos(2,n)
    Ví dụ: Ta có tập khoá là các giá trị số gồm 3 chữ số, và vùng nhớ cho bảng địa chỉ có khoảng 100 mục, như vậy ta sẽ lấy hai số cuối của khoá để làm địa chỉ theo phép chia lấy dư cho 100 : chẳng hạn 325 Mod 100 = 25
    Tuy nhiên ta nhận thấy nếu hàm băm dùng công thức như trên thì địa chỉ của khoá tính được chỉ căn cứ và 2 ký số cuối. Vì thế, để hàm băm có thể tính địa chỉ khoá một cách “ngẫu nhiên” hơn ta nên chọn m=97 thay vì 100
    c. Hàm băm sử dụng phương pháp nhân
    • Sử dụng công thức
    h(k) = floor(m (k A mod 1))
    k là khóa, m là kích thước bảng, A là hằng số: 0 < A < 1
    • Chọn m và A
    Ta thường chọn m = 2n
    Theo Knuth chọn A = 1/2(sqrt(5) -1)  0.618033987 được xem là tốt.
    d. Dùng hàm băm phổ quát
    Một tập các hàm băm H là phổ quát (universal ) nếu hH và 2 khoá k, l ta có xác suất: Pr{h(k) = h(l)} <= 1/m ,• với m là kích thước bảng
    Để xác suất xảy ra đụng độ thấp, khởi tạo một tập các hàm băm H phổ quát và từ đó h được chọn ngẫu nhiên.
    Ví dụ: Giả sử nếu khoá là một số nguyên, dương và HK(key) là một số nguyên với một digit từ 0..9, Thế thì, hàm băm sẽ dùng toán tử modulo-10 để trả về giá trị tương ứng của một khoá. Chẳng hạn: nếu khoá=49 thì HF(49)=9.

  5. #5
    Ngày gia nhập
    05 2007
    Nơi ở
    HCMC
    Bài viết
    60

    Bảng băm đóng : mỗi khóa ứng với một địa chỉ, thời gian truy xuất là hằng số
    Bảng băm mở : một số khóa có cùng địa chỉ, lúc này mỗi mục địa chỉ sẽ là một danh sách liên kết các phần tử có cùng địa chỉ, thời gian truy xuất có thể bị suy giảm đôi chút
    À, tại sonhn dùng tiếng Tây nên soda_chanhmuoi hổng thấy. Kỹ thuật băm Linear-probing gọi là băm đóng, còn Buckets gọi là băm mở.

    Thật ra, chỉ có bảng băm đóng mới có độ phức tạp tìm kiếm là O(1) (tối thiểu = tối đa). Còn bảng băm mở thì độ phức tạp tối thiểu là O(1), và còn có thế lớn hơn khi bảng băm có nhiều sự đụng độ
    Độ phức tạp giải thuật mà cũng có thuật ngữ "tối đa tối thiểu" nữa cơ à?

  6. #6
    Ngày gia nhập
    01 2007
    Bài viết
    412

    Mặc định Lập trình tìm kiếm | Tìm kiếm với mảng băm (hashtable): ý tưởng & cài đặt

    Trích dẫn Nguyên bản được gửi bởi sonhn Xem bài viết
    Độ phức tạp giải thuật mà cũng có thuật ngữ "tối đa tối thiểu" nữa cơ à?
    Có chứ, ý của neverland là:
    tối thiểu = độ phức tạp thuật toán trong trường hợp tốt nhất
    tối đa = độ phức tạp thuật toán trong trường hợp tệ nhất
    Chắc tại mình nói hơi khác nên làm bạn khó hiểu, cho xin lỗi nhé.

  7. #7
    Ngày gia nhập
    08 2006
    Nơi ở
    TpHCM
    Bài viết
    202

    Trích dẫn Nguyên bản được gửi bởi soda_chanhmuoi Xem bài viết
    Bảng băm đóng : mỗi khóa ứng với một địa chỉ, thời gian truy xuất là hằng số
    Bảng băm mở : một số khóa có cùng địa chỉ, lúc này mỗi mục địa chỉ sẽ là một danh sách liên kết các phần tử có cùng địa chỉ, thời gian truy xuất có thể bị suy giảm đôi chút
    Không biết bảng băm đóng là gì, nhưng theo định nghĩa mỗi khóa ứng với một địa chỉ, thì bảng băm này không có thực, chắc là bảng băm lý thuyết

  8. #8
    Ngày gia nhập
    01 2007
    Bài viết
    412

    Trích dẫn Nguyên bản được gửi bởi nguyentuan2 Xem bài viết
    Không biết bảng băm đóng là gì, nhưng theo định nghĩa mỗi khóa ứng với một địa chỉ, thì bảng băm này không có thực, chắc là bảng băm lý thuyết
    Có thể hiểu bảng băm đóng là bảng băm không xảy ra đụng độ, bởi thế với chỉ 1 phép ánh xạ là ta đã tìm ra được địa chỉ chứa khóa
    Chính xác là dạng bảng băm này có thực, nhưng rất rất ít được dùng tới vì tính phi khả thi của nó

  9. #9
    Ngày gia nhập
    04 2007
    Bài viết
    16

    Có thực chứ bạn, nhưng ứng dụng thì không gặp nhiều mà thôi.
    Thực ra mở rộng hash table, nó có thể lưu trữ một đối tượng bất kỳ tìm vào hàm băm của mình chứ không chỉ là string.
    Cài đặt bàng băm cũng có 2 kiểu thông dụng, phố biến nhất là dùng Linked List, rồi đến dùng mảng, mình thường dùng mảng hơn vì dùng Linked List sử dụng con trỏ nên tốc độ chậm hơn rất nhiều. Dùng mảng thì có rất nhiều cách cài đặt, cài đặt giống Forward Start trong đồ thị hoặc cài đặt bằng mảng 2 -> nhiều chiều , cũng có thể cài đặt theo kiểu cây - đây là cách cài đặt khá tốt

  10. #10
    Ngày gia nhập
    05 2007
    Nơi ở
    HCMC
    Bài viết
    60

    có thể lưu trữ một đối tượng bất kỳ tìm vào hàm băm của mình chứ không chỉ là string
    Tán thành! vì string cũng là đối tượng và mọi đối tượng đều có thể chuyển về dạng string.
    vì dùng Linked List sử dụng con trỏ nên tốc độ chậm hơn rất nhiều
    Cái này mình cho rằng chưa đúng. Theo mình, dùng con trỏ cho tốc độ truy xuất nhanh hơn và tận dụng bộ nhớ tốt hơn. Bản thân mảng trong C/C++ cũng được trình biên dịch chuyển về dạng con trỏ để xử lý.

Các đề tài tương tự

  1. Bảng băm (HashTable) thực hiện trên C
    Gửi bởi neverland87 trong diễn đàn Thắc mắc CTDL & Giải thuật
    Trả lời: 8
    Bài viết cuối: 04-03-2013, 09:36 AM
  2. Xin ví dụ về bảng băm -hashtable
    Gửi bởi faq.c trong diễn đàn Nhập môn lập trình C#, ASP.NET
    Trả lời: 4
    Bài viết cuối: 27-10-2012, 03:44 AM
  3. Lý thuyết tìm kiếm | Bảng băm ( hash table )
    Gửi bởi hailoc12 trong diễn đàn Thủ thuật, Tutorials CTDL & Giải thuật
    Trả lời: 5
    Bài viết cuối: 16-10-2012, 10:50 AM
  4. Xử lý nút tìm kiếm 1 phần tử trên HashTable như thế nào?
    Gửi bởi thegioi911 trong diễn đàn Thắc mắc lập trình C#
    Trả lời: 7
    Bài viết cuối: 05-05-2010, 11:55 AM
  5. Hàm tìm kiếm trên bảng băm, mong được giúp đỡ???
    Gửi bởi crazy_froghp trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 1
    Bài viết cuối: 25-05-2009, 05:39 AM

Quyền hạn của bạn

  • Bạn không thể gửi đề tài mới
  • Bạn không thể gửi bài trả lời
  • Bạn không thể gửi các đính kèm
  • Bạn không thể chỉnh sửa bài viết của bạn