Software Engineering Stack Exchange
Software Engineering Stack Exchange

Questions tagged [hashtable]

22 questions
53
votes
4 answers

What is the difference between a hash and a dictionary?

What is the difference between Hash and Dictionary? Coming from a scripting background, I feel that they are similar, but I wanted to find out the exact differences. Googling did not help me much.
Sairam
  • 641
  • 1
  • 5
  • 8
8
votes
5 answers

Implementing a hash table with true concurrency

This was recently a question I was asked in a screening and it got me thinking. I never totally settled on how the conversation ended, and I did some digging. None of the answers I saw seemed satisfactory to me. The question is essentially "how…
kiss-o-matic
  • 235
  • 2
  • 5
5
votes
1 answer

How does cuckoo hashing guarantee O(1) lookups in presence of persistent hash collisions

Most hash table implementations guarantee O(1) average case but O(n) maximum case for lookup (where 'n' is the number of keys in the table). But Cuckoo Hashing is described as O(1) maximum. Apparently it achieves this by using two hash functions,…
Jules
  • 17,614
  • 2
  • 33
  • 63
4
votes
4 answers

The fastest method for removing duplicate files safety?

I have a huge amount of files (mostly documents like pdf ~80-90%, but also images, videos, webpages, audio etc.), somewhere around 3.8 millions of files which occupies ~7.8Tb of hard drive space on a 10Tb hdd. I have tested a lot of software from…
YoYoYo
  • 149
  • 5
3
votes
0 answers

java hashtable extending to support duplicates

I have to maintain an old application and have to extend some modules. There is an hashtable that is used for maintaining/holding some objects as representation of running (real) processes (don't see them as plain software processes). It was…
PaulEdison
  • 149
  • 2
3
votes
2 answers

How exactly indexing works in arrays?

I only know that index is faster but don't know why is it faster. Suppose I have an array int[] a = {2,3,6,7}. Then I will try to find the element at a[3] and the speed of this will be O(1). Why? How it will know that 3 is placed after 2 boxes? So…
Asif Mushtaq
  • 141
  • 1
  • 7
3
votes
1 answer

Hash Table with iterators as the keys, is this poor design and can I do this better?

I'm developing a program where twice I've found the solution to a problem was to use hash tables with iterators as keys and some other arbitrary type as the value. I found my self using this pattern in initially to deal with two data structures…
Krupip
  • 1,252
  • 11
  • 19
3
votes
1 answer

When should a general purpose hash table assume hash equality implies logical equality?

For a general purpose hash table that aims for both high performance and correctness, when, if ever, does it make sense to assume that hash equality implies logical equality? To lay some ground rules for the question, assume either that all inputs…
Praxeolitic
  • 1,604
  • 3
  • 15
  • 24
2
votes
2 answers

Load factor and prime number for hashing in HashTable

I am trying to design a HashTable from scratch. I am starting with an initial bucket size of 11 and trying to maintain a load factor 0.75. Java documentation mentions that whenever the number of items reaches the load factor the HashTable increases…
Rahul Wadhwani
  • 133
  • 4
1
vote
2 answers

Can you create a hash table made of binary trees?

For instance, if you have a hash table with the array of buckets 26 nodes long, one for each letter of the alphabet. You use that to keep track of names. So when a name "Jed" is added to the J linked list that already has "Jack" and "John", rather…
samcode1
  • 19
  • 1
1
vote
1 answer

Library with different runtime behaviour based on usage history (design question)

I want to design a hash table library that keeps usage statistics and based on how it is used will use different implementations at runtime. For example use a certain implementation for small size hash tables and a different one for large ones (or…
pooya13
  • 187
  • 1
  • 5
1
vote
3 answers

Can a hash table implement a relation which can't be viewed as a mapping?

A (partial or total) mapping from set S to T is a special relation between S and T. The difference between a mapping and a relation is that: a relation between S and T in general doesn't require that for each s in S, there exists no more than one…
Tim
  • 5,405
  • 7
  • 48
  • 84
0
votes
0 answers

CRC32C as hash for hashmap

So I've been looking around to find a suitable hash function for a hashmap. Currently the best one I've found was from xxhash and maybe murmur after that, but they excluded CRC32C which can be optimized greatly by using 3 64 bit parallel crc32c…
Niels
  • 9
  • 1
0
votes
1 answer

how to store the data for function f(time,length)

I have a function which has discrete time step ,discrete length from origin . These two give height of the function. For example at time 1.2sec , and length 5.5cm from origin height is 10cm. The step size of time is 0.4sec and length step size is…
Mokka Naresh
  • 19
  • 1
0
votes
1 answer

What is the space complexity of a Python dictionary?

If python dictionaries are essentially hash tables and the length of hashes used in the python dictionary implementation is 32 bits, that would mean that regardless of the number of key-value pairs that actually exist in any given dictionary the…
MShakeG
  • 127
  • 4
1
2