Questions tagged [hash-function]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
11
votes
1answer
725 views

Do 'reflexive' hash algorithms exist?

Is there a class of hash algorithms, whether theoretical or practical, such that an algorithm in the class might be considered 'reflexive' according a definition given below: hash1 = algo1 ( "input ...
3
votes
1answer
514 views

Collision Attacks, Message Digests and a Possible solution

I've been doing some preliminary research in the area of message digests. Specifically collision attacks of cryptographic hash functions such as MD5 and SHA-1, such as the Postscript example and X.509 ...
10
votes
2answers
1k views

How do I choose a functional dictionary data structure?

I've read a bit about the following data structures: Bagwell's Ideal Hash Tries Larson's Dynamic hash tables Red-Black trees Patricia trees ...and I'm sure there are a lot of others out there. I've ...
36
votes
4answers
9k views

Is there a hash function for a collection (i.e., multi-set) of integers that has good theoretical guarantees?

I'm curious whether there is a way to store a hash of a multi-set of integers that has the following properties, ideally: It uses O(1) space It can be updated to reflect an insertion or deletion in O(...
9
votes
2answers
919 views

What is the optimal data structure for a tree of maps.

I'm looking for a data structure, that is basically a tree of maps, where the map at each node contains some new elements, as well as the elements in its parent node's map. By map here I mean a ...
3
votes
1answer
259 views

How is DHT different than regular hash tables in context to data/node lookup?

How is DHT different than regular hash tables in context to data/node lookup? This (introduction, 3rd paragraph) paper says: First, in addition to the insertion and deletion of items, DHTs must ...
10
votes
2answers
798 views

Hashing sets of integers for inclusion testing

I'm looking for a hash function over sets H(.) and a relation R(.,.) such that if A is included in B then R(H(A), H(B)). Of course, R(.,.) must be easy to verify (constant time), and H(A) should be ...
5
votes
2answers
716 views

How is rebalancing of DHTs handled in case of failure or addition of new node?

I am reading about Dynamo-like DHT data storage applications like cassandra and project voldemort. I was curious, say: A new node is added to the cluster (since all the nodes are full) then the whole ...
14
votes
3answers
584 views

Associative hash mixing

Consider the lowly singly-linked list in a purely functional setting. Its praises have been sung from the mountain tops and will continue to be sung. Here I will address one among its many strengths ...
26
votes
3answers
14k views

What is the difference between a second preimage attack and a collision attack?

Wikipedia defines a second preimage attack as: given a fixed message m1, find a different message m2 such that hash(m2) = hash(m1). Wikipedia defines a collision attack as: find two arbitrary ...
16
votes
1answer
558 views

Why is it important that the secret is at the end when signing with MD5?

it is often said that when using the MD5 algorithm to sign some arbitrary information, the shared secret has to be at the end. Why?

1
2