2022 Developer Survey is open! Take survey.

Questions tagged [hashtable]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
-1 votes
1 answer
92 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 ...
user avatar
  • 147
1 vote
2 answers
134 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 ...
user avatar
0 votes
1 answer
117 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 ...
user avatar
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 ...
user avatar
  • 127
2 votes
2 answers
445 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 ...
user avatar
8 votes
5 answers
5k 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 ...
user avatar
0 votes
0 answers
98 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 ...
user avatar
  • 17
1 vote
1 answer
75 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 ...
user avatar
  • 187
3 votes
0 answers
62 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 ...
user avatar
0 votes
1 answer
454 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 ...
user avatar
  • 139
2 votes
2 answers
5k 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 ...
user avatar
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 ...
user avatar
  • 948
0 votes
1 answer
131 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 ...
user avatar
  • 159
0 votes
3 answers
316 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 &...
user avatar
0 votes
2 answers
824 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 ...
user avatar
  • 5,271
1 vote
3 answers
332 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 ...
user avatar
  • 5,271
3 votes
1 answer
297 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 ...
user avatar
  • 1,514
0 votes
0 answers
49 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' => '...
user avatar
4 votes
1 answer
850 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. ...
user avatar
  • 17.3k
53 votes
4 answers
56k 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.
user avatar
  • 641