Questions tagged [hashing]
A hash function is any algorithm that maps data of arbitrary length to data of a fixed length. The values returned by a hash function are called hash values, hash codes, hash sums, checksums or simply hashes. From Wikipedia: http://en.wikipedia.org/wiki/Hash_function
163
questions
1626
votes
11
answers
806k
views
Which hashing algorithm is best for uniqueness and speed?
Which hashing algorithm is best for uniqueness and speed? Example (good) uses include hash dictionaries.
I know there are things like SHA-256 and such, but these algorithms are designed to be secure,...
- 22.6k
142
votes
3
answers
25k
views
Where do "magic" hashing constants like 0x9e3779b9 and 0x9e3779b1 come from?
In code dealing with hash tables, I often find the constant 0x9e3779b9 or sometimes 0x9e3779b1. For example
hash = n * 0x9e3779b1 >>> 24
Why is this particular value used?
- 1,003
75
votes
2
answers
57k
views
Why do so many hashed and encrypted strings end in an equals sign?
I work in C# and MSSQL and as you'd expect I store my passwords salted and hashed.
When I look at the hash stored in an nvarchar column (for example the out the box aspnet membership provider). I've ...
- 3,386
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.
- 641
50
votes
8
answers
61k
views
Why almost no webpages hash passwords in the client before submitting (and hashing them again on the server), as to "protect" against password reuse?
There are many sites on the Internet that require login information, and the only way to protect against password reusing is the "promise" that the passwords are hashed on the server, which is not ...
- 618
44
votes
6
answers
26k
views
Is it more secure to hash a password multiple times?
I've read a few times that when storing passwords, it's good practice to 'double hash' the strings (eg. with md5 then sha1, both with salts, obviously).
I guess the first question is, "is this ...
- 667
26
votes
4
answers
6k
views
Why is the Git .git/objects/ folder subdivided in many SHA-prefix folders?
Git internally stores objects (Blobs, trees) in the .git/objects/ folder. Each object can be referenced by a SHA1 hash that is computed from the contents of the object.
However, Objects are not ...
- 4,589
26
votes
3
answers
13k
views
I'm trying to understand hash tables - can someone explain it to me - clearly?
I want to understand the correct use and implementation of hash tables in php (sorry).
I read somewhere that an in-experienced programmer created a hash table and then iterated through it. Now, I ...
- 453
19
votes
6
answers
5k
views
What makes a hashing algorithm "secure"?
After reading this interesting question, I felt like I had a good idea of which insecure hashing algorithm I'd use if I needed one, but no idea why I might use a secure algorithm instead.
So what is ...
- 3,381
16
votes
6
answers
6k
views
How to implement float hashing with approximate equality
Let's say we have the following Python class (the problem exists in Java just the same with equals and hashCode)
class Temperature:
def __init__(self, degrees):
self.degrees = degrees
...
- 269
15
votes
6
answers
1k
views
How to assure users that website and passwords are secure [closed]
On reliable websites I always see claims such as "All data is encrypted" or "All passwords are encrypted using 128bit encryption" and etc. However I have never come across a claim such as "All ...
- 151
15
votes
3
answers
5k
views
How do scalable bloom filters work?
I was reading up on scalable bloom filters and could not understand how each time a constituent bloom filters fills up, a new bloom filter with larger size is added.
The elements that contributed to ...
- 269
12
votes
2
answers
12k
views
Is it possible to speed up a hash table by using binary search trees for separate chaining?
I want to implement a Hash Table using Binary Search Trees to reduce the search complexity in the Separate Chaining process from O(n) (using linked list) to O(log n) (using BST). Can this be done, and ...
- 139
12
votes
6
answers
5k
views
Where should salt hash values come from?
When adding salt values to a hash value for something like a password that cannot be stored in plain text, what is the best place to get the salt values come from? For context, let us suppose this is ...
- 12.7k
12
votes
3
answers
2k
views
Is it possible to implement a well-distributed hash table without using the % operator?
I'm looking to implement a fast, well-distributed hash table in C#. I'm having trouble choosing my hash-constraining function that takes an arbitrary hash code and "constrains" it so it can be used to ...
- 358
11
votes
6
answers
4k
views
Is there an "anti-hash" or "similarity hash" / similarity measure algorithm?
The idea of hashes is they get drastically different results for even the smallest change of data.
What I am asking for is the opposite of that. An algorithm that will produce proximity hash values ...
- 673
11
votes
3
answers
10k
views
How does a web browser save passwords?
How do current web browsers (or mobile mail clients and any software in general) save user passwords? All answers about storing passwords say we should store only hashes, not the password themselves. ...
- 254
10
votes
5
answers
1k
views
If passwords are stored hashed, how would a computer know that your password is similar to the last one if you try resetting your password?
If passwords are stored hashed, how would a computer know that your password is similar to the last one if you try resetting your password? Wouldn't the two passwords be totally different since one is ...
- 125
9
votes
3
answers
28k
views
What are the advantages of linear probing over separate chaining or vice-versa when implementing hash tables?
I've been brushing up on algorithms and reviewed these two methods of implementing hash tables. It seems like they largely have similar performance characteristics and memory requirements.
I can ...
- 263
8
votes
2
answers
4k
views
Overriding GetHashCode in a mutable struct - What NOT to do?
I am using the XNA Framework to make a learning project. It has a Point struct which exposes an X and Y value; for the purpose of optimization, it breaks the rules for proper struct design, since its ...
- 436
8
votes
1
answer
2k
views
Hash function classification
On the internet, I've come across this question:
Classify the Hashing Functions based on the various methods by which the key value is found.
with answers like
Direct method
Subtraction method
...
- 2,613
8
votes
4
answers
3k
views
How to perform consistent hashing on any Python object that works with hash()?
I have a Python library that performs a kind of calculation given a parameter-object. A requirement of the parameter object is that it be both hashable and serializable. It's a long calculation, so it ...
- 345
7
votes
8
answers
7k
views
Using HashTable without overriding hashcode()
Today I was asked this question during an interview:
What will happen if we do not override the hashcode method for our
class, then add it to HashTable and then try to get objects?
What could go ...
- 443
7
votes
3
answers
8k
views
What is an example for a one-way hash function?
I am doing a bit of research on hash functions. I understand the concept that it is an equation that is easy to do one way (you take the number 00011010 for example and do reasonably simple math with ...
- 171
7
votes
4
answers
4k
views
Convert filenames to their checksum before saving to prevent duplicates. Is is a smart thing to do?
TL;DR:what the title says
I am developing some sort of image board in PHP. I was thinking of changing each image's filename to it's checksum prior to saving it. This way, I might be able to prevent ...
- 1,370
7
votes
1
answer
4k
views
Uniformly distributing GUIDS to bucket of size N [closed]
How can uniformly and deterministically distribute set of GUIDS to N buckets.
N can be as small as 2.
Need to make sure the same GUID is always mapped to the same bucket.
Can't use any additionally ...
- 181
7
votes
3
answers
822
views
Hashing growth strategy
What is a good growth strategy for hash tables? If the number of elements exceeds the number of buckets, I increase the number of buckets with the following formula:
n = int(n * 1.618033988749895) | ...
- 6,844
6
votes
2
answers
1k
views
History of Associative Array?
In quite a lot of modern scripting languages (e.g. Perl, Python, Ruby, PHP, Lua, JavaScript), associative arrays are supported as a primitive or first-class data type (with various names like map, ...
- 215
6
votes
2
answers
6k
views
Sorting versus hashing
My problem is as follows. I have an array of n strings with m < n of them distinct. I want to create a one-to-one function which assigns each of the m distinct strings to the numbers 0 ... m-1. ...
- 213
6
votes
3
answers
435
views
What is the benefit of caching a hash value in a string object?
I made a patch to a programming language run-time to cache the results of hashing a string in the string object, so that it is just retrieved the next time it is required.
However, I'm not convinced ...
- 3,554
6
votes
1
answer
355
views
Using account (login) password in generated PDF?
Ever since I heard about programming, I was told that any password (especially the one used on login) should be stored in database using any kind of one-way hashing algorithm, and never ever as plain ...
- 2,356
6
votes
1
answer
1k
views
How can I benchmark concurrent key-value stores?
I have some concurrent key-value store implementations that are implemented with hash tables and search trees that I would like to compare. I would like to benchmark them with a real world application ...
- 69
5
votes
5
answers
3k
views
How can I protect an SQL connection string in a client-side application?
I am developing a .NET Windows application and I need to make requests to a SQL Server instance. How do I secure the authentication data in my code in case someone decompiles my application?
I know ...
- 83
5
votes
3
answers
9k
views
How can I reverse engineer a hash code?
I am building an application in C# that works with a Progress database. The passwords that are stored in this database are stored using a hash algorithm that Progress has not made public. However, I ...
5
votes
5
answers
2k
views
Is it possible to insert the hash of an executable into the executable itself without changing the resulting hash? What's the best alternative?
I've been thinking about this problem recently and it really doesn't seem like it's possible, but I figured that I'd ask just in case.
Assume a simple program, in pseudocode:
run hash on an ...
- 53
5
votes
6
answers
3k
views
Would md5 hashes allow detection of synced files?
We have to develop our own file management system in Java web application. We need to sync files between our main server and client severs and find out whether all the client server has all the latest ...
- 51
5
votes
4
answers
524
views
Concept behind SHA-1 Checksum
What's the basis behind SHA-1 or SHA-2 or other Checksum algorithms?
I read about it here http://en.wikipedia.org/wiki/SHA-1#Data_Integrity
But I am still wondering about an answer in a layman's ...
- 1,871
5
votes
2
answers
12k
views
Finding duplicate files? [duplicate]
I am going to be developing a program that detects duplicate files and I was wondering what the best/fastest method would be to do this? I am more interested in what the best hash algorithm would be ...
- 304
5
votes
7
answers
3k
views
How do i speedily traverse a file system while extracting/extrapolating various data and provide user feedback?
I'm working on a system file scanner that reveals info about various files (e.g. size, last used, duplicates, etc). Currently I'm traversing the file system once just to get a good measure of the ...
- 193
5
votes
1
answer
10k
views
Hashing Algorithm: Deleting an element in linear probing
While using Linear probing method to implement hashing, when we delete and element, the position of the deleted element is declared as a tombstone/ mark it as deleted. Why can't we just shift all the ...
- 153
5
votes
1
answer
3k
views
Why would a Rest Api demand a hash of the parameters?
I'm working with a Rest Api that demands to send with any request a hash of the parameters of the request:
Hashkey Calculation This hash key has to be generated by the device
itself and has to ...
- 195
5
votes
1
answer
1k
views
Why use strong checksums to detect random errors in a filesystem like btrfs?
Btrfs supports crc32c, xxhash, sha256 and blake2b as checksums when storing and reading files. crc32c and xxhash are designed to detect random errors while sha256 and blake2 are considered ...
- 61
5
votes
1
answer
2k
views
What kind of members should be used in a GetHashCode() implementation
We're building some Roslyn analyzers concerning GetHashCode(), including an analyzer that implements it for you in a given class.
While researching the subject we've found that there are many ...
- 5,716
5
votes
1
answer
2k
views
Hash Algorithm Randomness Visualization
I'm curious if anyone here has any idea how the images were generated as shown in this response: Which hashing algorithm is best for uniqueness and speed?
Ian posted a very well-received response but ...
- 53
5
votes
1
answer
2k
views
Using PostgreSQL MD5 hash to calculate a 64 bit hash value for advisory lock functions?
I have a particular problem addressing the PostgreSQL advisory locking functions using the bigint variants.
Basically I want to create a 64 bit bigint value from a text type obtained with the ...
- 1,530
5
votes
0
answers
281
views
How to get a one-way hash function that is collision safe for about 1 million unique inputs? [duplicate]
Forgive me if this is a noob question - My CS education is a somewhat incomplete
Basically, I need a way to hash an input, so that someone seeing the output doesn't see the original input value. ...
- 207
4
votes
3
answers
457
views
How to store (and find) updated values in a Distributed Hash Table?
Distributed Hash Tables are a great way to store immutable data in a resilient way.
However, I am wondering about how it would be possible to store new versions of old data in this system.
Because ...
- 4,589
4
votes
2
answers
2k
views
How can "hash functions" be used to implement hash maps at all?
My understandment is that hash maps allow us to link, say, a string, to certain memory location. But if every string were to be linked to a unique place in memory it would need a huge block of empty ...
- 5,780
4
votes
4
answers
364
views
Preventing password hashing algorithm from overloading CPU
These days password hashing algorithms are designed to be slow. While it prevents black hats from guessing the password (at least partially), it also gives additional work for the server.
I can ...
- 977
4
votes
1
answer
5k
views
Directory structure (file system design)
I was looking at how file systems are designed and noticed that most places say that the directory hierarchy can be implemented using a hash table.
Could someone please explain me how using a hash ...
- 43