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

learn more… | top users | synonyms

3
votes
2answers
127 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 ...
669
votes
9answers
223k 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 ...
0
votes
1answer
59 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 ...
-1
votes
1answer
94 views

Can someone please explain reverse look up tables? [closed]

Im finding it difficult to understand reverse look up tables and how it works, and the concept of hash chains. This is apart of a computer security model i am taking. So i understand that brute force, ...
17
votes
6answers
2k 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
votes
1answer
74 views

Should changes to FNV-1A's input exhibit the avalanche effect?

This is kind of related to Which hashing algorithm is best for uniqueness and speed?. In that question, the excellently written top answer notes, Randomnessification The other subjective ...
1
vote
1answer
80 views

Garbage collection & memory leaks on hash tables

I was reading R. Read's How to be a programmer, and I came accross something I didn't understand: ...even with garbage collection, you can fill up all memory with garbage. A classic mistake is ...
3
votes
3answers
112 views

sorting / merging hashtable

For my project I have a hashtable with 1M buckets (sometimes more). Each bucket contains lots of values and they are stored sorted in a dynamic array. I am looking for easy enough way to store all ...
-1
votes
1answer
77 views

What are some hashmaps we can easily implement? [duplicate]

At many places, I read that we can use HashMap here for O(1) search. Actually, I want to ask how I can implement easy hashmaps which can satisfy this property. Can anyone tell few hashmaps including ...
24
votes
8answers
21k 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?

Relevant XKCD 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, ...
3
votes
1answer
182 views

Hash function with uniqueness guarantees and controllable entropy

Is there a class of hash functions that meets the following specs: Upper and lower bound can be specified Uniqueness is guaranteed as long as the input is between the upper and lower bounds Amount ...
0
votes
2answers
101 views

How early does a hashable type need to become immutable?

Suppose I have a class that looks vaguely like this: class Foo(object): _value = None # XXX: see below def __init__(self, value): self._value = value @property def ...
0
votes
2answers
104 views

Track a series of choices with a single number

I want to track a series of scored questions in a single number (the total score). Is that possible? and how? For example, I have 30 questions with either 3 or 2 choices. For any given question, the ...
0
votes
0answers
68 views

Does multiple Bloom filters make sense?

In order to decrease the number of false positives, I came up with a couple of possible solutions. Create two different types of Bloom filters; eg. filter1 using 3 different hash algorithms, filter2 ...
4
votes
0answers
127 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. ...
1
vote
2answers
102 views

Is hash calculated before/after compression?

I had a question regarding compression and calculation of checksum/hash of data. I would like to know if checksum has to be calculated before or after the compression of data before transmission. ...
1
vote
2answers
116 views

Is there a known standard data structure which is a hash table that resolves collisions using a binary tree?

Is there a known standard data structure which is a hash table that resolves collisions using a binary tree? If so what is the name of this data structure? I imagine such a structure would be useful ...
6
votes
2answers
1k 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 ...
1
vote
2answers
431 views

Why a hashtable? Why not just a non-hashed associative array?

I've been learning about using a hashtable to efficiently check for items in a list without looping through the whole thing, but there's one thing that I don't get: Why hashed keys? It seems like: ...
1
vote
2answers
483 views

What's the shortest generating one-way hash algorithm?

I have a 24 character long id which is guaranteed to be unique. I would like to shorten that to 7-10 (or even shorter) characters long. If I generate an short id randomly then I would have to check ...
0
votes
1answer
32 views

Hash function for progressive changes

I am looking for a hashing algorithm that works like this. I start with a text file, and compute its hash. Now I know that I will remove one character at, say, position 67 and this character is a "m", ...
0
votes
1answer
765 views

Complexity of ArrayList of LinkedHashSet

I get input strings from the console like this: while ((currentLine = bufferedReader.readLine()) != null ) { StringTokenizer string = new StringTokenizer(currentLine, " "); while ...
38
votes
2answers
6k 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
votes
4answers
110 views

Can I save & store a user's submission in a way that proves that the data has not been altered, and that the timestamp is accurate?

There are many situations where the validity of the timestamp attached to a certain post (submission of information) might be invaluable for the post owner's legal usage. I'm not looking for a service ...
4
votes
2answers
605 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 ...
1
vote
1answer
158 views

Measuring “novelty” of data

I have a heuristic in mind that should allow me to "score" data based on "novelty" that I would like to work in real-ish time. In this case, I mean novelty in the sense that the data source is ...
0
votes
2answers
50 views

Hashing + security as it pertains to a theoretical file sharing site

These days it's possible to hash a file client-side, send the hash to the server, and have the server check whether or not that file is already uploaded. If it is, we can skip the file upload and make ...
8
votes
6answers
3k 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 ...
0
votes
2answers
231 views

Randomized Hash function with no collisions

Related to the question Which hashing algorithm is best for uniqueness and speed? Is there a way to create a hash function, or find one, whose hash length depends completely on the input length, has ...
1
vote
3answers
313 views

what is the javascript internal data structure?

Consider a basic js object: var obj={x:1,y:'2'}; Is this stored internally as a hashtable or does js use a different mechanism for key value pairs? If they are hash tables does anyone know how they ...
2
votes
2answers
1k views

Design Hash table with simple hash function

I want to learn to Design Hash table with simple hash function for better understanding. I understand that the hash table will work as long as the hash function maps each key to a non-negative integer ...
0
votes
1answer
129 views

Why Num&sizeMinusOne faster than num&(size-1)

I've been told that when I have a hash table of size m and m=2^k, I can use the & operator as num & (size-1) instead of num % size, to fit the hashCode to my table size. I've also been told ...
4
votes
2answers
994 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 ...
0
votes
2answers
111 views

How do crackers determine number of iterations of a Hashing algorithm?

Does a cracker need to know the number of iterations a hashing algorithm uses to compute a hash? If they don't know it, how do they figure it out? How much longer does it take to figure it out, than ...
0
votes
2answers
275 views

How deterministic are SessionIDs from SHA'd GUIDs?

Assume I'm using the following code to generate pseudo-random sessionID's: sessionID = SHA-512(GENERATE-GUID()) The GUIDs are pretty deterministic, i.e. I see lots of GUIDs with a lot of the same ...
2
votes
3answers
927 views

Optimal way to implement this specific lookup table in C#?

I want to create a lookup table for this data: The "input variables" (what is used to "lookup") are 4 different doubles that can each take on 1 of 200 numbers (the numbers range from 1-1000 but there ...
1
vote
2answers
911 views

Data Aggregation of CSV files java

I have k csv files (5 csv files for example), each file has m fields which produce a key and n values. I need to produce a single csv file with aggregated data. I'm looking for the most efficient ...
3
votes
2answers
306 views

Would using rainbow tables to detect weak user passwords feasible?

As I understand in most security breach where the list of hashed password are compromised, attackers do use brute-force to try to find weak password and, invariably, they always find quite some (like ...
2
votes
4answers
462 views

Looking for monotonically increasing (integer) hash function

I'm looking for a HashFunction(X,Y: Integer): Integer that is monotonically increasing on X, then Y. So: HashFunction(x1,y1) > HashFunction(x2,y2) if x1>x2 HashFunction(x,y1) > HashFunction(x,y2) if ...
21
votes
6answers
6k 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 ...
4
votes
4answers
251 views

Is there a name for the concept of a “cumulative checksum”?

Insofar as I understand it, tools like Git and Mercurial derive checksums from their data, and those checksums are used to derive other checksums used in aggregate, leading to a kind of accumulative ...
5
votes
1answer
954 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 ...
14
votes
6answers
959 views

How to assure users that website and passwords are secure [on hold]

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 ...
5
votes
1answer
798 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. ...
5
votes
3answers
2k 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 ...
2
votes
4answers
286 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 ...
5
votes
1answer
342 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 ...
1
vote
1answer
621 views

ruby-idiomatic hashes vs arrays

So I am still fairly new to ruby, though I have noticed that it is very hard to create 2d-array and that hashes seem to be more of the go to data structure than arrays. I was wondering why the Ruby ...
1
vote
2answers
1k 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 ...
4
votes
6answers
1k 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 ...