Questions tagged [hashtable]
The hashtable tag has no usage guidance.
21
questions
0
votes
0
answers
91
views
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 ...
- 9
0
votes
1
answer
121
views
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 ...
CommunityBot
- 1
-1
votes
1
answer
151
views
A data structure / algorithm to combine search tree and hash table?
I have a two dimensional data with one dimension is ordered and another one is categorical, for example, country and city_age:
country
age
city
Italy
2773
Rome
Germany
784
Berlin
USA
397
New York
...
- 23.1k
1
vote
2
answers
365
views
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 ...
- 12.3k
0
votes
1
answer
2k
views
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 ...
- 10.3k
2
votes
2
answers
728
views
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 ...
- 40.9k
8
votes
5
answers
6k
views
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 ...
- 8,841
0
votes
0
answers
106
views
Searching/Hashing Wikipedia - at each position for keys 1..31 long, the fastest way?
A C coder here.
My wish is to find the best way to search words and phrases within the ever-growing English Wikipedia XML dump. As a first layer/step, hashing is the answer, yes?
The problem is that ...
- 17
1
vote
1
answer
77
views
Library with different runtime behaviour based on usage history (design question) [closed]
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 ...
- 187
3
votes
0
answers
65
views
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 ...
- 149
0
votes
1
answer
494
views
Logic Behind a Basic Hash Table Hashing Algorithm
I am trying to write a Hash Table in Java based on some Princeton article about it.
The most commonly used method for hashing integers is called modular
hashing: we choose the array size M to be ...
- 3,904
3
votes
2
answers
6k
views
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 ...
- 2,295
53
votes
4
answers
58k
views
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.
- 13k
3
votes
1
answer
1k
views
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 ...
- 1,232
0
votes
1
answer
142
views
What is the opposite of the 'load factor' (in reference to hash tables)
When the load of the hash table grows too large in proportion to the hash table size, you increase the size of the hash table to improve performance. When the load is too large is dependant on a ...
- 2,552
0
votes
3
answers
352
views
What can I infer from Hilbert's map?
How do I understand Hilbert's map in this answer? The author of the answer has mapped the hash value (integer) of some strings to a 2D image. I understand that Hilbert's curve is a technique for 1D &...
- 12.3k
0
votes
2
answers
894
views
Can hashtable be used for implementing multimap?
Is it correct that hashtables assume no key is shared between more
than one records?
In other words, can hashtables be used for implementing multimaps?
When using a hashtable, can't multiple records ...
- 328
1
vote
3
answers
349
views
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 ...
- 1,319
3
votes
1
answer
328
views
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 ...
CommunityBot
- 1
0
votes
0
answers
54
views
Reverse lookup of data based on user input
I have an array in the format:
$array = array(
0 => array(
'name' => 'Item 1',
'level' => 1,
'points' => 10
),
1 => array(
'name' => '...
- 151
4
votes
1
answer
986
views
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. ...
- 21.6k