Created
June 14, 2017 14:37
-
-
Save prydt/ec7d3696b47bf93476cbb0cec3bee510 to your computer and use it in GitHub Desktop.
A simple chaining HashTable in Kotlin
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
package prydt.source | |
/** | |
* A HashTable | |
* Created by PryDt 6/14/2017. | |
*/ | |
// a key-value pair | |
data class HashPair<Key, T>(val key: Key, val item: T) | |
// HashTable Class | |
class HashTable<Key, T : Any> { | |
// the full length of the table | |
val length = 13 | |
// the how many pairs are in the table | |
val size = 0 | |
// the internal table of arraylists of pairs | |
val table = arrayOfNulls<ArrayList<HashPair<Key, T>>>(length) | |
// initalize data structure | |
init { | |
// sets the whole table to arraylists | |
for(i in table.indices) | |
{ | |
table.set(i, ArrayList<HashPair<Key, T>>(0)) | |
} | |
} | |
// insert into hashtable | |
fun insert(key: Key, item: T) | |
{ | |
val index = hash(key) | |
table.get(index)?.add(HashPair<Key, T>(key, item)) | |
} | |
// just an alias for a command | |
// returns null if failed delete | |
fun delete(key: Key) : T? | |
{ | |
return delete(key, null); | |
} | |
// deletes item w/ given key from hashtable | |
// default return value is what it will return if it fails | |
fun delete(key: Key, defaultReturn: T? = null) : T? | |
{ | |
val index = hash(key) | |
if(table.get(index)?.size != 0) | |
{ | |
val iter = table.get(index)?.iterator() | |
while(iter!!.hasNext()) | |
{ | |
val pair = iter.next() | |
if(pair.key == key) | |
{ | |
iter.remove() | |
return pair.item | |
} | |
} | |
} | |
// delete failed... return default value | |
return defaultReturn | |
} | |
// print out table | |
fun printTable() | |
{ | |
println("{") | |
for(i in table) | |
{ | |
if(i!!.size > 0) | |
{ | |
val iter = i.iterator() | |
while(iter.hasNext()) | |
{ | |
val pair = iter.next(); | |
println("\t${pair.key}\t:\t${pair.item}") | |
} | |
} | |
} | |
println("}"); | |
} | |
// hash object of type T using hashCode() function | |
infix fun hash(obj: Key) : Int | |
{ | |
// can't hash null value | |
if(obj == null) return -1 | |
// return hash | |
return (obj.hashCode() and 0x7fffffff) % length | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
class HashTable<Key, T> {
private val table = mutableListOf<Pair<Key, T>?>()
var size = 0
private set
}