LISP - Bảng băm
Cấu trúc dữ liệu bảng băm đại diện cho một tập hợp key-and-valuecác cặp được tổ chức dựa trên mã băm của khóa. Nó sử dụng khóa để truy cập các phần tử trong bộ sưu tập.
Bảng băm được sử dụng khi bạn cần truy cập các phần tử bằng cách sử dụng một khóa và bạn có thể xác định một giá trị khóa hữu ích. Mỗi mục trong bảng băm có một cặp khóa / giá trị. Chìa khóa được sử dụng để truy cập các mục trong bộ sưu tập.
Tạo bảng băm trong LISP
Trong Common LISP, bảng băm là một tập hợp có mục đích chung. Bạn có thể sử dụng các đối tượng tùy ý làm khóa hoặc các chỉ mục.
Khi bạn lưu trữ một giá trị trong bảng băm, bạn tạo một cặp khóa-giá trị và lưu trữ nó dưới khóa đó. Sau đó, bạn có thể lấy giá trị từ bảng băm bằng cách sử dụng cùng một khóa. Mỗi khóa ánh xạ đến một giá trị duy nhất, mặc dù bạn có thể lưu trữ một giá trị mới trong một khóa.
Bảng băm, trong LISP, có thể được phân loại thành ba loại, dựa trên cách các khóa có thể được so sánh - eq, eql hoặc bằng. Nếu bảng băm được băm trên các đối tượng LISP thì các khóa sẽ được so sánh với eq hoặc eql. Nếu bảng băm băm trên cấu trúc cây, thì nó sẽ được so sánh bằng cách sử dụng bằng nhau.
Các make-hash-tablehàm được sử dụng để tạo bảng băm. Cú pháp cho hàm này là:
make-hash-table &key :test :size :rehash-size :rehash-thresholdỞ đâu -
Các key đối số cung cấp khóa.
Các :testđối số xác định cách các khóa được so sánh - nó phải có một trong ba giá trị # 'eq, #' eql, hoặc # 'bằng nhau hoặc một trong ba ký hiệu eq, eql hoặc bằng. Nếu không được chỉ định, eql được giả định.
Các :sizeđối số đặt kích thước ban đầu của bảng băm. Đây phải là một số nguyên lớn hơn 0.
Các :rehash-sizeđối số chỉ định mức tăng kích thước của bảng băm khi nó đầy. Đây có thể là một số nguyên lớn hơn 0, là số mục nhập cần thêm hoặc nó có thể là một số dấu phẩy động lớn hơn 1, là tỷ lệ của kích thước mới với kích thước cũ. Giá trị mặc định cho đối số này phụ thuộc vào việc triển khai.
Các :rehash-thresholdđối số chỉ định mức độ đầy đủ mà bảng băm có thể nhận được trước khi nó phải phát triển. Đây có thể là một số nguyên lớn hơn 0 và nhỏ hơn: rehash-size (trong trường hợp này, nó sẽ được chia tỷ lệ bất cứ khi nào bảng được tăng lên) hoặc nó có thể là một số dấu phẩy động từ 0 đến 1. Giá trị mặc định cho giá trị này đối số phụ thuộc vào việc triển khai.
Bạn cũng có thể gọi hàm make-hash-table không có đối số.
Lấy các mục từ và thêm các mục vào bảng băm
Các gethashhàm lấy một mục từ bảng băm bằng cách tìm kiếm khóa của nó. Nếu nó không tìm thấy khóa, thì nó sẽ trả về nil.
Nó có cú pháp sau:
gethash key hash-table &optional defaultở đâu -
key: là khóa liên quan
bảng băm: là bảng băm cần tìm kiếm
default: là giá trị được trả về, nếu không tìm thấy mục nhập, giá trị này là nil, nếu không được chỉ định.
Các gethash hàm thực sự trả về hai giá trị, giá trị thứ hai là giá trị vị từ đúng nếu tìm thấy mục nhập và sai nếu không tìm thấy mục nhập.
Để thêm một mục vào bảng băm, bạn có thể sử dụng setf chức năng cùng với gethash chức năng.
Thí dụ
Tạo một tệp mã nguồn mới có tên main.lisp và nhập mã sau vào đó.
(setq empList (make-hash-table))
(setf (gethash '001 empList) '(Charlie Brown))
(setf (gethash '002 empList) '(Freddie Seal))
(write (gethash '001 empList))
(terpri)
(write (gethash '002 empList))Khi bạn thực thi mã, nó trả về kết quả sau:
(CHARLIE BROWN)
(FREDDIE SEAL)Xóa mục nhập
Các remhashhàm xóa bất kỳ mục nhập nào cho một khóa cụ thể trong bảng băm. Đây là một vị từ đúng nếu có mục nhập hoặc sai nếu không có.
Cú pháp của hàm này là:
remhash key hash-tableThí dụ
Tạo một tệp mã nguồn mới có tên main.lisp và nhập mã sau vào đó.
(setq empList (make-hash-table))
(setf (gethash '001 empList) '(Charlie Brown))
(setf (gethash '002 empList) '(Freddie Seal))
(setf (gethash '003 empList) '(Mark Mongoose))
(write (gethash '001 empList))
(terpri)
(write (gethash '002 empList))
(terpri)
(write (gethash '003 empList))
(remhash '003 empList)
(terpri)
(write (gethash '003 empList))Khi bạn thực thi mã, nó trả về kết quả sau:
(CHARLIE BROWN)
(FREDDIE SEAL)
(MARK MONGOOSE)
NILHàm maphash
Các maphash hàm cho phép bạn áp dụng một hàm được chỉ định trên mỗi cặp khóa-giá trị trên bảng băm.
Nó cần hai đối số - hàm và một bảng băm và gọi hàm một lần cho mỗi cặp khóa / giá trị trong bảng băm.
Thí dụ
Tạo một tệp mã nguồn mới có tên main.lisp và nhập mã sau vào đó.
(setq empList (make-hash-table))
(setf (gethash '001 empList) '(Charlie Brown))
(setf (gethash '002 empList) '(Freddie Seal))
(setf (gethash '003 empList) '(Mark Mongoose))
(maphash #'(lambda (k v) (format t "~a => ~a~%" k v)) empList)Khi bạn thực thi mã, nó trả về kết quả sau:
3 => (MARK MONGOOSE)
2 => (FREDDIE SEAL)
1 => (CHARLIE BROWN)