Home › Đời Sống › Hash table là gì

Hash table là gì

09:57, 06/04/2021

Lớp 1-2-3

Lớp 1

Lớp 2

Vsống bài xích tập

Lớp 3

Vsinh hoạt bài tập

Đề kiểm tra

Lớp 4

Sách giáo khoa

Sách/Vlàm việc bài xích tập

Đề kiểm tra

Lớp 5

Sách giáo khoa

Sách/Vở bài tập

Đề kiểm tra

Lớp 6

Sách giáo khoa

Sách/Vsinh sống bài xích tập

Đề kiểm tra

Chuyên đề và Trắc nghiệm

Lớp 7

Sách giáo khoa

Sách/Vsinh hoạt bài tập

Đề kiểm tra

Chuyên ổn đề & Trắc nghiệm

Lớp 8

Sách giáo khoa

Sách/Vngơi nghỉ bài bác tập

Đề kiểm tra

Chulặng đề & Trắc nghiệm

Lớp 9

Sách giáo khoa

Sách/Vngơi nghỉ bài bác tập

Đề kiểm tra

Chulặng đề và Trắc nghiệm

Lớp 10

Sách giáo khoa

Sách/Vsinh hoạt bài bác tập

Đề kiểm tra

Chulặng đề và Trắc nghiệm

Lớp 11

Sách giáo khoa

Sách/Vsống bài bác tập

Đề kiểm tra

Chuyên ổn đề & Trắc nghiệm

Lớp 12

Sách giáo khoa

Sách/Vnghỉ ngơi bài tập

Đề kiểm tra

Chuim đề và Trắc nghiệm

Ngữ pháp Tiếng Anh

Lập trình Java

Phát triển web

Lập trình C, C++, Python

Cơ sở dữ liệu

Cấu trúc tài liệu với giải thuậtMột số khái niệm về Giải thuật Cấu trúc dữ liệu mảng (Array)Danh sách links - Linked ListsNgăn xếp và Hàng đợiMột số Giải thuật tra cứu kiếmMột số Giải thuật sắp tới xếpCấu trúc tài liệu vật dụng thị (Graph)Cấu trúc tài liệu câyĐệ qui (Recursion)Tài liệu tìm hiểu thêm
Cấu trúc dữ liệu Hash Table
Trang trước
Trang sau

Hash Table là gì?

Cấu trúc tài liệu Hash Table là 1 trong những cấu tạo tài liệu lưu lại dữ liệu theo cách thức phối hợp. Trong Hash Table, dữ liệu được giữ lại trong định dạng mảng, trong các số ấy những cực hiếm tài liệu có giá trị chỉ mục riêng biệt. Việc truy vấn dữ liệu trlàm việc bắt buộc nhanh rộng trường hợp chúng ta biết chỉ mục của tài liệu đề nghị search.

Bạn đang xem: Hash table là gì

Do kia, với các loại kết cấu dữ liệu Hash Table này thì các vận động cyếu cùng chuyển động search tìm sẽ ra mắt hết sức nhanh hao, bỏ mặc kích cỡ của dữ liệu là bao nhiêu. Hash Table sử dụng mảng nhỏng là 1 trong kho gìn giữ trung gian với thực hiện chuyên môn Hash để chế tạo chỉ mục trên địa điểm bộ phận được chèn vào.

Kỹ thuật Hashing

Hashing là 1 trong những kỹ thuật để thay đổi một hàng những quý hiếm khóa (key) vào vào một dãy các quý giá chỉ mục (index) của một mảng. Chúng ta vẫn sử dụng tân oán tử mang phần dư nhằm thu được một dãy các giá trị khóa. Giả sử có một HashTable có kích thước là trăng tròn, và bên dưới đấy là những thành phần cần phải gìn giữ. Phần tử vào định hình (key, value).

(1,20)(2,70)(42,80)(4,25)(12,44)(14,32)(17,11)(13,78)(37,98)SttKeyHashChỉ mục mảng

1	1	1 % đôi mươi = 1	1
2	2	2 % đôi mươi = 2	2
3	42	42 % trăng tròn = 2	2
4	4	4 % đôi mươi = 4	4
5	12	12 % đôi mươi = 12	12
6	14	14 % 20 = 14	14
7	17	17 % trăng tròn = 17	17
8	13	13 % 20 = 13	13
9	37	37 % 20 = 17	17

Kỹ thuật Dò tuyến tính (Linear Probing)

Chúng ta thấy rằng hoàn toàn có thể xảy ra ngôi trường thích hợp cơ mà nghệ thuật Hashing được áp dụng nhằm tạo chỉ mục vẫn trường thọ vào mảng. Trong tình huống này, chúng ta đề xuất kiếm tìm kiếm địa điểm trống kế tiếp vào mảng bởi Việc quan sát vào vào ô tiếp theo cho tới lúc bọn họ search thấy một ô trống. Kỹ thuật này được điện thoại tư vấn là Dò đường tính (Linear Probing).

SttKeyHashChỉ mục mảngSau chuyên môn Linear Probing, chỉ mục mảng

1	1	1 % trăng tròn = 1	1	1
2	2	2 % 20 = 2	2	2
3	42	42 % đôi mươi = 2	2	3
4	4	4 % 20 = 4	4	4
5	12	12 % đôi mươi = 12	12	12
6	14	14 % đôi mươi = 14	14	14
7	17	17 % trăng tròn = 17	17	17
8	13	13 % đôi mươi = 13	13	13
9	37	37 % đôi mươi = 17	17	18

Các hoạt động cơ bạn dạng trên Hash Table

Dưới đấy là một trong những vận động cơ phiên bản có thể được tiến hành trên cấu tạo dữ liệu Hash Table.

Hoạt đụng tìm kiếm kiếm: tra cứu kiếm một trong những phần tử vào cấu trúc tài liệu HashTable.

Hoạt rượu cồn chèn: chèn 1 phần tử vào trong kết cấu tài liệu HashTable.

Hoạt đụng xóa: xóa 1 phần tử từ bỏ cấu tạo dữ liệu HashTable.

Phần tử dữ liệu (DataItem) trong HashTable

Phần tử tài liệu bao gồm: data với key. Dựa vào key này chúng ta cũng có thể triển khai các hoạt động search kiếm vào kết cấu dữ liệu HashTable.

Xem thêm: Bàn Chân Lạnh Là Bệnh Gì - Bị Lạnh Chân Vào Mùa Đông Có Sao Không

struct DataItem int data; int key;;

Phương thơm thức của kết cấu dữ liệu Hash Table

Xác định một phương thức để khoảng chừng Hash Code của key của phần tử tài liệu.

int hashCode(int key) return key % SIZE;

Hoạt hễ kiếm tìm tìm vào Hash Table

Mỗi Lúc một phần tử được search kiếm: khoảng chừng cực hiếm hash code của key đang truyền vào cùng tiếp nối xác định vị trí của thành phần bởi vì sử dụng cực hiếm hash code kia giống như là chỉ mục vào mảng. Sử dụng chuyên môn Dò con đường tính (Linear Probing) để lấy thành phần nếu như không tìm thấy thành phần với mức giá trị hash code vẫn ước tính.

struct DataItem *search(int key) //rước quý giá hash int hashIndex = hashCode(key); //dịch chuyển trong mảng cho tới khi gặp mặt ô trống while(hashArray != NULL) if(hashArray->key == key) return hashArray; //cho tới ô tiếp sau ++hashIndex; //bảo phủ hash table hashIndex %= SIZE; return NULL; Để theo dõi code đầy đủ các chuyển động trong Hash Table, mời các bạn nhấn vào vào chương: Hash Table vào C.

Hoạt cồn chèn trong Hash Table

Mỗi Khi một phần tử được chèn: ước lượng cực hiếm hash code của key vẫn truyền và xác xác định trí của phần tử vì chưng sử dụng cực hiếm hash code đó y hệt như là chỉ mục vào mảng. Sử dụng Dò tuyến tính (Linear Probing) mang lại địa chỉ trống nếu như bộ phận được search thấy với mức giá trị hash code đang ước chừng.

void insert(int key,int data) struct DataItem *cửa nhà = (struct DataItem*) malloc(sizeof(struct DataItem)); item->data = data; item->key = key; //Lấy quý hiếm hash int hashIndex = hashCode(key); //di chuyển vào mảng cho tới khi chạm mặt ô trống hoặc bị xóa while(hashArray != NULL &và hashArray->key != -1) //tới ô tiếp sau ++hashIndex; //bao bọc hash table hashIndex %= SIZE; hashArray = item; Để quan sát và theo dõi code không hề thiếu những hoạt động vào Hash Table, mời bạn bấm vào vào chương: Hash Table vào C.

Hoạt động xóa vào Hash Table

Mỗi Lúc một phần tử cần được xóa: ước lượng quý giá hash code của key vẫn truyền vào cùng sau đó xác xác định trí của bộ phận bởi áp dụng quý hiếm hash code đó y hệt như là chỉ mục vào mảng. Sử dụng Dò đường tính (Linear Probing) để mang thành phần trường hợp nhỏng không kiếm thấy bộ phận với mức giá trị hash code sẽ ước lượng. khi search thấy, tàng trữ một trong những phần tử mang trên phía trên để giữ hiệu suất của hash table.

struct DataItem* delete(struct DataItem* item) int key = item->key; //đem giá trị hash int hashIndex = hashCode(key); //di chuyển vào mảng cho tới lúc gặp gỡ ô trống while(hashArray !=NULL) if(hashArray->key == key) struct DataItem* temp = hashArray; //gán 1 phần tử giả tại địa chỉ bị xóa hashArray = dummyItem; return temp; //tới ô tiếp theo sau ++hashIndex; //phủ bọc hash table hashIndex %= SIZE; return NULL; Để theo dõi code không hề thiếu những chuyển động trong Hash Table, mời các bạn bấm vào vào chương: Hash Table vào C.

Đã có app VietJaông chồng trên điện thoại cảm ứng thông minh, giải bài tập SGK, SBT Soạn vnạp năng lượng, Văn uống chủng loại, Thi online, Bài giảng....miễn tổn phí. Tải ngay lập tức áp dụng trên Android và iOS.

Follow fanpage của team https://www.facebook.com/aiesec-unwe.netteam/ hoặc facebook cá nhân Nguyễn Tkhô cứng Tuyền https://www.facebook.com/tuyen.vietjaông xã để liên tục theo dõi và quan sát những loạt bài mới nhất về Java,C,C++,Javascript,HTML,Pyeo hẹp,Database,Mobile.... mới nhất của Cửa Hàng chúng tôi.