Emacs Lisp Tutorial

Emacs Lisp Tutorial: Hash Table

Advertise Here

, ,

This page shows you how to use hash table in emacs lisp. If you don't know elisp, first take a look at Emacs Lisp Basics.

What Are Hash Tables

Often, you need to have a list with elements being key-value pairs. For example, the key may be a person's name, and the value can be their age. Or, in a more complex case, the key can be the person's ID number, and the value can be a data of name, age, sex, phone number, address, etc. You might have thousands of such entries, and you want to be able to know that, given a ID, find out whether it exists in your data. You also want to be able to add or delete, modify entries in the data.

From a interface point of view, such a keyed list looks like this: ((key1 value1) (key2 value2) (key3 value3) …). If you want to know a particular key exist, you can write a loop thru the list to test if any first element of a element matches your given key. Similarly, you can add a entry by appending to the list, or delete and modify the list using your language's list-manipulation operators or functions. All this functionality is provided in elisp, called Association List.

(info "(elisp) Association Lists")

However, this method will be too slow to the point of unusable if you have thousands of entries and frequently need to check, add, delete, or modify the data. This is because most languages are not smart enough to analyze your use of list to determine how best to compile it in the language. The solution provided in most high-level languages of today is to provide a particular data type (called a hash table), so that when you want to use a list of huge number of pairs with fast lookup, you use that data type.

For example, here's how hash table looks like in some high-level languages:

# perl
%mydata = ("mary"=> 4, "jane"=> 5, "vicky"=>7);

# PHP
$mydata = array("mary"=> 4, "jane"=> 5, "vicky"=> 7);

# Python
mydata = {"mary":4, "jane":5, "vicky":7}

(See: Keyed List in Python and Perl, PHP: Keyed List) Similarly, elisp provides a hash table data type.

Note: Hash table is also known as hash, keyed-list, dictionary, map. It's called hash table for historical reasons. Basically, a technique to create fast-lookup of a data, is by using a so-called hash-function, that converts the key into a unique (randomish) number. So that, instead of going thru the huge list to check every item, you just check one particular memory address to see whether it exists. Such a function is called “hash-function” because its key-conversion operation is analogous to processing a type of food dish made by disorderly and irreversibly chopping up and mixing up veggies or meat. (See: Hash function, Hash (food), Hash browns. )

(If your data needs tens of thousand or millions of entries, the proper solution is to use a Relational Database.)

Hash Table in Emacs Lisp

To create a hash table, use (make-hash-table :test 'equal).

Here's a complete code that shows how to create a hash table, then add, change, remove, entries:

(let (myHash val)

  ;; create a hash table
  (setq myHash (make-hash-table :test 'equal))

  ;; add entries
  (puthash "mary" "19" myHash)
  (puthash "jane" "20" myHash)
  (puthash "carrie" "17" myHash)
  (puthash "liz" "21" myHash)

  ;; modify a entry's value
  (puthash "jane" "16" myHash)

  ;; remove a entry
  (remhash "liz" myHash)

  ;; get a entry's value
  (setq val (gethash "jane" myHash))

  (message val) ; print it
)

In the above example, the entry's keys and values are both “string” data type. However, elisp's hash table can have any lisp datatype as the key or value.

When we create a hash table, we used :test 'equal to let elisp know that the function equal should be used when testing whether a key exists. If your keys are other lisp data type, you need to specify which equality functon emacs should use to test if a key exist. The available value for :test are 'eql, 'eq, 'equal. (You can also define your own equality test.)

To clear all entries in a hash table, use (clrhash ‹myHash›).

To get a count of entries in hash table, use (hash-table-count myHash).

Check If a Key Exists

To check if a key exists, use the (gethash ‹myKey› ‹myHash›). If it exists, its value is returned, else “nil” is returned. Example:

(let (myHash)
  (setq myHash (make-hash-table :test 'equal))
  (puthash 'mary "19" myHash)

  (gethash 'vicky myHash) ; returns nil
)

gethash has a optional third parameter “default”. If the key does not exist, “default” is returned.

Apply a Function to All Key-Value Pairs

To apply a function to all entries in a hash table, use (maphash ‹myfun› ‹myHashtable›). The function “myfun” must take 2 arguments, key and value. For example, if you want a list of all keys, you can write a function that puts the key into a list, then print out the list. We show several examples below.

Get All Keys

To get all keys into a list, we can use a maphash with a function that pulls the keys into a list. Here's a example:

;; example of getting all keys from a hash table

;; creating a hash
(defvar myHash (make-hash-table :test 'equal))
(puthash "mary" "19" myHash)
(puthash "jane" "20" myHash)
(puthash "carrie" "17" myHash)
(puthash "liz" "21" myHash)

;; get all keys
(defvar allkeys '())

(defun pullkeys (kk vv)
  "prepend the key “kk” to the list “allkeys”"
  (setq allkeys (cons kk allkeys))
)

(maphash 'pullkeys myHash)

In the above example, “pullkeys” is used only once. Since it is used only once, we don't need to define it separately, but just use lambda construct. So, the maphash line can be just like this: (maphash (lambda (kk vv) (setq allkeys (cons kk allkeys))) myHash).

You can define a “keys” function that returns all keys of a given hash table. Like this:

(defun keys (hashtable)
  "Return all keys in hashtable."
  (let (allkeys)
    (maphash (lambda (kk vv) (setq allkeys (cons kk allkeys))) hashtable)
    allkeys
  )
)

With this function, you can use it like this: (keys myHash).

Get All Values

Getting all values is just like getting all keys above. Here's a function that does it.

(defun hash-values (hashtable)
  "Return all values in HASHTABLE."
  (let (allvals)
    (maphash (lambda (kk vv) (setq allvals (cons vv allvals))) hashtable)
    allvals
  )
)

Print All Entries Sorted By Key

Here's a example how you can print out all entries in a hash table by sorted key.

First, we define a function that turns a hash table into a list.

(defun hash-to-list (hashtable)
  "Return a list that represent the HASHTABLE."
  (let (myList)
    (maphash (lambda (kk vv) (setq myList (cons (list kk vv) myList))) hashtable)
    myList
  )
)
;; example of turning a hash table into list then sort it
(let (myHash myList)

  ;; add items to the hash
  (setq myHash (make-hash-table :test 'equal))
  (puthash "mary" "19" myHash)
  (puthash "jane" "20" myHash)
  (puthash "carrie" "17" myHash)
  (puthash "liz" "21" myHash)

  ;; get the hash table into a list
  (setq myList (hash-to-list myHash))

  ;; sort and print it out
  (sort myList (lambda (a b) (string< (car a) (car b))))
)

;; prints (("carrie" "17") ("jane" "20") ("liz" "21") ("mary" "19"))

Warning: elisp's sort function is destructive. Once sort is used on a variable, that variable's value is essentially destroyed. (the sorted result is returned.) If you want to keep the variable, make a copy first.

(info "(elisp) Rearrangement")

Hash Table with Lisp Objects

Elisp's hash table's key or value can be any lisp object. Also, you can define your own equality test, as well as providing few other parameters when creating a hash table. For detail, see elisp manual.

(info "(elisp) Hash Tables")

Emacs ♥

blog comments powered by Disqus