Skip to content

Instantly share code, notes, and snippets.

@micahcantor
Created January 2, 2021 05:17
Show Gist options
  • Save micahcantor/332b2952187402a01cb1aee8600949a9 to your computer and use it in GitHub Desktop.
Save micahcantor/332b2952187402a01cb1aee8600949a9 to your computer and use it in GitHub Desktop.
An implementation of mutable hash tables in Racket
#lang racket/base
(require math/number-theory)
#| An implentation of mutable hash maps with string keys in Racket |#
#| "Private" Functions |#
(struct hash (table [num #:auto])
#:mutable
#:auto-value 0)
; Returns the index for a given string key
(define (hash-func key size)
(let ([initial 17] [mult 13])
(modulo
(+ initial
(for/sum ([char key]) (* mult (char->integer char))))
size)))
; Resizes a hash table to avoid collisions.
(define (hash-resize! hash)
(let* ([old-size (vector-length (hash-table hash))]
[new-size (next-prime (* 2 old-size))]
[new-table (build-vector new-size (λ (n) null))])
(for* ([lst (hash-table hash)]
[pair lst]
#:unless (null? lst))
(let* ([idx (hash-func (car pair) new-size)]
[lookup (vector-ref new-table idx)])
(vector-set! new-table idx (cons (cons (car pair) (cdr pair))
lookup))))
(set-hash-table! hash new-table)))
#| "Public" Functions |#
; Creates an empty hash table
(define (make-hash)
(let ([size 3])
(hash (build-vector size (λ (n) null)))))
; Returns the value associated with key in hash
(define (hash-get hash key)
(let* ([table (hash-table hash)]
[idx (hash-func key (vector-length table))])
(cdr (findf (λ (pair) (equal? key (car pair)))
(vector-ref table idx)))))
; Sets the value in hash associated with key.
(define (hash-set! hash key value)
(set-hash-num! hash (add1 (hash-num hash)))
(let ([load-factor (/ (hash-num hash) (vector-length (hash-table hash)))])
(when (> load-factor .8)
(hash-resize! hash)))
(let* ([table (hash-table hash)]
[idx (hash-func key (vector-length table))]
[lookup (vector-ref table idx)])
(vector-set! table idx (cons (cons key value) lookup))))
#| Testing |#
(define my-table (make-hash))
(hash-table my-table) ; --> '#(() () ())
(vector-length (hash-table my-table)) ; --> 3 (initial size)
(hash-set! my-table "key1" "value1")
(hash-set! my-table "key2" "value2")
(hash-set! my-table "key3" "value3")
(hash-table my-table) ; --> '#(() (("key3" . "value3")) (("key2" . "value2")) (("key1" . "value1")) () () ())
(vector-length (hash-table my-table)) ; --> 7 (next prime after doubling 3)
(provide make-hash hash-get hash-set!)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment