Skip to content

Instantly share code, notes, and snippets.

@prydt
Created June 14, 2017 14:37
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save prydt/ec7d3696b47bf93476cbb0cec3bee510 to your computer and use it in GitHub Desktop.
Save prydt/ec7d3696b47bf93476cbb0cec3bee510 to your computer and use it in GitHub Desktop.
A simple chaining HashTable in Kotlin
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
}
}
@NonCoderF
Copy link

NonCoderF commented Jan 1, 2023

class HashTable<Key, T> {
private val table = mutableListOf<Pair<Key, T>?>()
var size = 0
private set

fun insert(key: Key, item: T) {
    val index = key.hashCode() % table.size
    table[index] = Pair(key, item)
    size++
}

fun delete(key: Key): T? {
    val index = key.hashCode() % table.size
    val result = table[index]?.second
    if (result != null) size--
    table[index] = null
    return result
}

}

@NonCoderF
Copy link

in less lines

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment