PasteRack.org
Paste # 86793
2020-05-13 13:50:15

Fork as a new paste.

Paste viewed 233 times.


Embed:

  1. #lang racket
  2. ;;; TESTS ;;;
  3.  
  4.  
  5.  
  6.  
  7. ;;; CODES ;;;
  8. ;;; Procedure
  9. ;;;   add
  10. ;;; Parameters:
  11. ;;;   key, a string
  12. ;;;   val, a value
  13. ;;;   table, a vector containing the hash table
  14. ;;; Purpose:
  15. ;;;   insert a new key value pair into the hash table
  16. (define add
  17.   (lambda (key val table)
  18.     (let* ([index (hash table key)]
  19.            [elements (getElements table)]
  20.            [element (vector-ref elements index)])
  21.       (cond [(keyExists key element)
  22.              (cond [(null? element)
  23.                     (incrementTally table)])
  24.              (vector-set! elements index (cons (list key val) element))
  25.              (when (> (getLoadFactor table) 0.5)
  26.                       (resize table))]
  27.             [else (display "the key already exists")]))))
  28.  
  29. ;;; Procedure
  30. ;;;   update
  31. ;;; Parameters:
  32. ;;;   key, a string
  33. ;;;   val, a value
  34. ;;;   table, a vector containing the hash table
  35. ;;; Purpose:
  36. ;;;   update the value corresponding to the given key in the hash table
  37. (define update
  38.   (lambda (key val table)
  39.     (let* ([index (hash table key)]
  40.            [elements (getElements table)]
  41.            [element (vector-ref elements index)])
  42.       (cond [(not (keyExists key element))
  43.              (vector-set! elements index (updateHelper key val element))]
  44.             [else (display "the key does not exist")]))))
  45.  
  46. ;;; Procedure
  47. ;;;   find
  48. ;;; Parameters:
  49. ;;;   key, a string
  50. ;;;   table, a vector containing the hash table
  51. ;;; Purpose:
  52. ;;;   find the val corresponding to the given key in table and return the element
  53. (define find
  54.   (lambda (key table)
  55.     (let* ([index (hash table key)]
  56.            [element (vector-ref (getElements table) index)])
  57.       (let kernel ([remaining element])
  58.         (cond [(null? remaining)
  59.                (display "the key does not exist")]
  60.               [(string=? key (car (car remaining)))
  61.                (car remaining)]
  62.               [else (kernel (cdr remaining))])))))
  63.  
  64. ;;; Procedure
  65. ;;;   delete
  66. ;;; Parameters:
  67. ;;;   key, a string
  68. ;;;   table, a vector containing the hash table
  69. ;;; Purpose:
  70. ;;;   deletes the key value pair from the table
  71. (define delete
  72.   (lambda (key table)
  73.     (let* ([index (hash table key)]
  74.            [elements (getElements table)]
  75.            [element (vector-ref elements index)])
  76.       (cond [(not (keyExists key element))
  77.              (vector-set! elements index (deleteHelper key element))
  78.              (when (null? (cdr element))
  79.                (decrementTally table))]
  80.             [else (display  "the key already exists")]))))
  81.  
  82. ;;; Procedure
  83. ;;;   resize
  84. ;;; Parameters:
  85. ;;;   table, a vector containing the hash table
  86. ;;; Purpose:
  87. ;;;   doubles the size of the given table
  88. (define resize
  89.   (lambda (table)
  90.     (let* ([size (getSize table)]
  91.            [alphabet-size (getAlphabetSize table)]
  92.            [elements (vector-take (getElements table) size)]
  93.            [new-elements (make-vector (* 2 size) (list))])
  94.       (vector-set! table 1 (* 2 size))
  95.       (vector-set! table 0 new-elements)
  96.       (vector-set! table 2 0)
  97.       (let kernel ; rehash every pair
  98.         ([counter 0])
  99.         (when (< counter size)
  100.           (resizeHelper table (vector-ref elements counter))
  101.           (kernel (+ 1 counter)))))))
  102.  
  103.  
  104. ;;; HELPERS ;;;
  105. ;;; Procedure
  106. ;;;   create
  107. ;;; Parameters:
  108. ;;;   size, an integer
  109. ;;;   alphabet-size, an integer indicating the size of our alphabet
  110. ;;; Purpose:
  111. ;;;   creates a new hash table
  112. (define create
  113.   (lambda (size alphabet-size)
  114.     (vector (make-vector size (list)) size 0 alphabet-size)))
  115. ;;; Procedure
  116. ;;;   hash
  117. ;;; Parameters:
  118. ;;;   key, a string
  119. ;;;   table, a vector containing the hash table
  120. ;;; Purpose:
  121. ;;;   calculates the hash value of the key with regard of the table
  122. (define hash
  123.   (lambda (table key)
  124.     (let ([len (string-length key)]
  125.           [size (getSize table)]
  126.           [alphabet-size (getAlphabetSize table)])
  127.       (let kernel ([counter 0]
  128.                    [hash-so-far 0]
  129.                    [coef (expt alphabet-size (- len 1))])
  130.         (if (>= counter len)
  131.             (modulo hash-so-far size)
  132.             (kernel
  133.              (+ counter 1)
  134.              (+ hash-so-far
  135.                 (* (char->integer (string-ref key counter))
  136.                    coef))
  137.              (/ coef alphabet-size)))))))
  138. ;;; Procedure
  139. ;;;   deleteHelper
  140. ;;; Parameters:
  141. ;;;   key, a string
  142. ;;;   element, the element in which key is found
  143. ;;; Purpose:
  144. ;;;   Deletes key and its corresponding val from element
  145. ;;; Produces:
  146. ;;;   pair, a list containing key and val just deleted
  147. (define deleteHelper
  148.   (lambda (key element)
  149.     (let kernel ([remaining element]
  150.                  [so-far (list)])
  151.       (if (string=? key (get-key (car remaining)))
  152.           (append so-far (cdr remaining))
  153.           (kernel (cdr remaining)
  154.                   (cons (car remaining) so-far))))))
  155. ;;; Procedure
  156. ;;;   updateHelper
  157. ;;; Parameters:
  158. ;;;   key, a string
  159. ;;;   val, a value
  160. ;;;   element, the entry, the key value pair
  161. ;;; Purpose:
  162. ;;;  update the val corresponding to the given key in the element
  163. (define updateHelper
  164.   (lambda (key val element)
  165.     (let kernel ([remaining element]
  166.                  [so-far (list)])
  167.       (if (string=? key (car (car remaining)))
  168.           (append (cons (list key val) so-far)
  169.                   (cdr remaining))
  170.           (kernel (cdr remaining)
  171.                   (cons (car remaining) so-far))))))
  172. ;;; Procedure
  173. ;;;   resizeHelper
  174. ;;; Parameters:
  175. ;;;   table, a vector containing the hash table
  176. ;;;   element, an entry in the table
  177. ;;; Purpose:
  178. ;;;   rehashes elements to the resized table
  179. (define resizeHelper
  180.   (lambda (table element)
  181.     (let kernel ([remaining element])
  182.       (when (not (null? remaining))
  183.         (add (car (car remaining)) (cadr (car remaining)) table)
  184.         (kernel (cdr remaining))))))
  185. ;;; Procedure
  186. ;;;   keyExists
  187. ;;; Parameters:
  188. ;;;   key, a string
  189. ;;;   element, an entry of the table
  190. ;;; Purpose:
  191. ;;;   determine if a key exists in a hash table
  192. ;;; Produces:
  193. ;;;   return true if the key already exists false otherwise
  194. (define keyExists
  195.   (lambda (key element)
  196.     (let kernel ([remaining element])
  197.       (cond [(null? remaining) #t]
  198.             [(string=? (car (car remaining)) key) #f]
  199.             [else (kernel (cdr remaining))]))))
  200. ;;; Procedure
  201. ;;;   getElements
  202. ;;; Parameters:
  203. ;;;   table, a vector containing hash table
  204. ;;; Purpose:
  205. ;;;   get all elements from the table
  206. (define getElements
  207.   (lambda (table)
  208.     (vector-ref table 0)))
  209. ;;; Procedure
  210. ;;;   getSize
  211. ;;; Parameters:
  212. ;;;   table, a vector containing hash table
  213. ;;; Purpose:
  214. ;;;  get the size of the table
  215. (define getSize
  216.   (lambda (table)
  217.     (vector-ref table 1)))
  218. ;;; Procedure
  219. ;;;   get-occupied-elements-count
  220. ;;; Parameters:
  221. ;;;   table, a vector containing hash table
  222. ;;; Purpose:
  223. ;;;   determines the number of occupied elements of the hash table
  224. ;;; Produces:
  225. ;;;   count, an integer representing the number of occupied elements
  226. ;;;(define get-occupied-elements-count
  227.   ;(lambda (table)
  228.    ; (vector-ref table 2)))
  229.  
  230. ;;; Procedure
  231. ;;;   getAlphabetSize
  232. ;;; Parameters:
  233. ;;;   table, a vector containing hash table
  234. ;;; Purpose:
  235. ;;;   get the alphabet size of the hash table
  236. (define getAlphabetSize
  237.   (lambda (table)
  238.     (vector-ref table 3)))
  239. ;;; Procedure
  240. ;;;   incrementTally
  241. ;;; Parameters:
  242. ;;;   table, a vector containing hash table
  243. ;;; Purpose:
  244. ;;;   increments the total counts of occupied spaces in the hash table
  245. (define incrementTally
  246.   (lambda (table)
  247.     (vector-set! table 2 (+ (vector-ref table 2) 1))))
  248. ;;; Procedure
  249. ;;;   decrementTally
  250. ;;; Parameters:
  251. ;;;   table, a vector containing hash table
  252. ;;; Purpose:
  253. ;;;   decrements the total counts of occupied spaces in the hash table
  254. (define decrementTally
  255.   (lambda (table)
  256.     (vector-set! table 2 (- (vector-ref table 2) 1))))
  257. ;;; Procedure
  258. ;;;   getLoadFactor
  259. ;;; Parameters:
  260. ;;;   table,a vector containing hash table
  261. ;;; Purpose:
  262. ;;;  gets load factor of the hash table
  263. (define getLoadFactor
  264.   (lambda (table)
  265.     (exact->inexact (/ (vector-ref table 2) (getSize table)))))
  266.  
  267. (define table (create 4 94))
  268. table
  269. (hash table "A")

=>

'#(#(() () () ()) 4 0 94)

1