Look at hash array mapped tries, which is what most functional languages use to implement hashmaps.