How to find the threshold of hash inequality at a given time?

For a miner to mine in bitcoin, he should find a nonce s.t the hash of block <= threshold. At a given time lets assume the total hash rate of the network be A hashes/sec and the mining rate be f blocks/sec. Is there way any to calculate this threshold from these parameters?

hash map – Open-addressed C hashmap

I implemented an open-addressed, double-hashed hashmap in C, now looking for some advice on improving it. Thank you.

hashmap.h:

#pragma once

#include <stdbool.h>

typedef struct hm_hashmap_t *hm_hashmap_t;

hm_hashmap_t hm_init(void);
void hm_destroy(hm_hashmap_t hm);

void hm_set(hm_hashmap_t hm, const char *key, void *val);
void *hm_get(hm_hashmap_t hm, const char *key);
void hm_delete(hm_hashmap_t hm, const char *key);

typedef struct hm_iterator_t *hm_iterator_t;

hm_iterator_t hm_iteratorInit(hm_hashmap_t hm);
void hm_iteratorDestroy(hm_iterator_t iter);

bool hm_iteratorNext(hm_iterator_t iter);
char *hm_iteratorKey(hm_iterator_t iter);
void *hm_iteratorVal(hm_iterator_t iter);

hashmap.c:

#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

#include "hashmap.h"
#include "hashfuncs.h"

#define INITIAL_BASE_SIZE 100

#define PRIME1 151
#define PRIME2 163

#define HIGH_DENSITY 70

typedef struct
{
  char *key;
  void *value;
} hm_item;

struct hm_hashmap_t
{
  long size;
  long count;
  hm_item **items;
};

struct hm_iterator_t
{
  hm_hashmap_t hm;
  long cursor;
  bool finished;
  char *key;
  void *val;
};

static hm_item HM_DELETED_ITEM = {NULL, NULL};

enum itemType
{
  empty,
  deleted,
  normal
};

static long sizes() = {1009, 2027, 8111, 16223, 32467, 64937, 129887, 259781, 519577, 1039169, 2078339, 4156709, 8313433, 16626941, 33253889};

static int currentSizeIndex = 0;

#define sizeLength sizeof(sizes) / sizeof(sizes(0))

typedef struct
{
  long index;
  enum itemType type;
} itemIndex;

/*
 * private methods
*/

static hm_item *hm_newItem(const char *k, void *v)
{
  hm_item *item = malloc(sizeof(hm_item));
  item->key = strdup(k);
  item->value = v;
  return item;
}

static hm_hashmap_t hm_initSized(const int newSize)
{
  hm_hashmap_t hm = malloc(sizeof(*hm));
  hm->size = newSize;
  hm->count = 0;
  hm->items = calloc((size_t)hm->size, sizeof(hm_item *));

  return hm;
}

static void hm_resize(hm_hashmap_t hm, const long newSize)
{
  if (newSize >= sizes(sizeLength - 1))
  {
    return;
  }

  hm_hashmap_t tmpHm = hm_initSized(newSize);
  if (tmpHm == NULL)
  {
    return; // if there wasn't enough memory, just return
  }

  for (int i = 0; i < hm->size; i++)
  {
    hm_item *item = hm->items(i);
    if (item != NULL && item != &HM_DELETED_ITEM)
    {
      hm_set(tmpHm, item->key, item->value);
    }
  }

  hm->count = tmpHm->count;

  const long tmpSize = hm->size;
  hm->size = tmpHm->size;
  tmpHm->size = tmpSize;

  hm_item **tmpItems = hm->items;
  hm->items = tmpHm->items;
  tmpHm->items = tmpItems;

  hm_destroy(tmpHm);
}

static itemIndex hm_findItemIndex(hm_hashmap_t hm, const char *key)
{
  long index = strHash(key, PRIME1, hm->size);

  hm_item *item = hm->items(index);

  int i = 1;
  while (item != NULL)
  {
    if (item == &HM_DELETED_ITEM)
    {
      return (itemIndex){index, deleted};
    }
    else if (strcmp(item->key, key) == 0)
    {
      return (itemIndex){index, normal};
    }

    index = strDoubleHash(key, hm->size, PRIME1, PRIME2, i);
    item = hm->items(index);
    i++;

    if (i > hm->size)
    {
      // out of memory
      exit(1);
    }
  }
  return (itemIndex){index, empty};
}

static void hm_deleteItem(hm_item *item)
{
  free(item->key);
  free(item);
}

static void hm_iteratorFindNext(hm_iterator_t it)
{
  long cur = it->cursor + 1;
  while (cur < it->hm->size)
  {
    if (it->hm->items(cur) != NULL && it->hm->items(cur) != &HM_DELETED_ITEM)
    {
      it->cursor = cur;
      it->key = it->hm->items(cur)->key;
      it->val = it->hm->items(cur)->value;
      return;
    }

    ++cur;
  }

  it->finished = true;
}

/*
 * public methods
*/

hm_hashmap_t hm_init()
{
  return hm_initSized(sizes(0));
}

void hm_destroy(hm_hashmap_t hm)
{
  for (long i = 0; i < hm->size; i++)
  {
    hm_item *item = hm->items(i);
    if (item != NULL && item != &HM_DELETED_ITEM)
    {
      hm_deleteItem(item);
    }
  }
  free(hm->items);
  free(hm);
}

void hm_set(hm_hashmap_t hm, const char *key, void *value)
{
  itemIndex i = hm_findItemIndex(hm, key);

  if (i.type == normal)
  {
    free(hm->items(i.index)->value);
    hm->items(i.index)->value = value;

    return;
  }

  hm_item *item = hm_newItem(key, value);
  hm->items(i.index) = item;
  hm->count++;

  long long load = hm->count * 100 / hm->size;
  if (load > HIGH_DENSITY && currentSizeIndex < (int)(sizeLength - 1))
  {
    hm_resize(hm, sizes(++currentSizeIndex));
  }
}

void *hm_get(hm_hashmap_t hm, const char *key)
{
  itemIndex i = hm_findItemIndex(hm, key);
  return i.type == empty || i.type == deleted ? NULL : hm->items(i.index)->value;
}

void hm_delete(hm_hashmap_t hm, const char *key)
{
  itemIndex i = hm_findItemIndex(hm, key);

  if (i.type == empty || i.type == deleted)
  {
    return;
  }

  hm_deleteItem(hm->items(i.index));
  hm->items(i.index) = &HM_DELETED_ITEM;
  hm->count--;
}

hm_iterator_t hm_iteratorInit(hm_hashmap_t hm)
{
  hm_iterator_t it = malloc(sizeof(*it));
  it->hm = hm;
  it->cursor = -1;
  it->finished = false;

  return it;
}

void hm_iteratorDestroy(hm_iterator_t iter)
{
  free(iter);
}

bool hm_iteratorNext(hm_iterator_t iter)
{
  if (iter->finished)
    return false;

  hm_iteratorFindNext(iter);
  return !iter->finished;
}

char *hm_iteratorKey(hm_iterator_t iter)
{
  return iter->hm->items(iter->cursor)->key;
}

void *hm_iteratorVal(hm_iterator_t iter)
{
  return iter->hm->items(iter->cursor)->value;
}

hashfuncs.h:

#pragma once

long strHash(const char *s, const int p, const long m);

long strDoubleHash(const char *s, const long m, const int p1, const int p2, const int numAttempts);

hashfuncs.c:

long strHash(const char *s, const int p, const long m) {
    long long hashValue = 0;
    long long pPow = 1;
    while(*s != '') {
        hashValue = (hashValue + *s++ * pPow) % m;
        pPow = (pPow * p) % m;
    }
    return hashValue;
}

long strDoubleHash(const char *s, const long m, const int p1, const int p2, const int numAttempts) {
    const long hash1 = strHash(s, p1, m);
    if (numAttempts == 0) {
      return hash1;
    }
    else {
      const long hash2 = strHash(s, p2, m);
      return (hash1 + (numAttempts * (p2 - hash2 % p2))) % m;
    }
}
```

Number of minimal perfect hash functions that are order preserving- why is it true?

Suppose we have a universe of $u=|U|$ elements. We called a set of $H$ function $(U,m)$ order-preserving minimal perfect hash family (OPMPHF) if for every subset $Msubset U$ of size $m$ has at least one function $hin H$ which is an over preserving minimal prefect hash. It is shown in (1,2) that for every
$(U,m)$-OPMPHF $H$ obeys:

$$H=m! cdot {u choose m}/(frac{u}{m})^m $$

Thus, the program length for any order preserving minimal perfect hash function should contain at least $log_2 |H|$ bits.

In partiular, if $m=3,u=8$, we have that $|H|geq 17.7$.

However, I think I can create as set of $|H|=6$ functions for such family. For every $2leq ileq 7$ we define $f_i(x)$ to be equal $1$ if $x<i$, equal $2$ if $x=i$ and equal $3$ if $xgeq i$. Every function $f_i$ is order-preserving, and for each set $M$ with second element $i$ has a perfect function $f_i$.

Do I miss something in my analysis?

(1)- http://160592857366.free.fr/joe/ebooks/ShareData/Optimal%20algorithms%20for%20minimal%20perfect%20hashing.pdf
(2)-K. Mehlhorn. Data Structures and Algorithms 1: Sorting and Searching,
volume 1. Springer-Verlag, Berlin Heidelberg, New York, Tokyo, 1984

I implemented my own version of hash table in java with arrays and linear probing

I did some manual tests by instantiating the class and it seems to be working okay. I wanted some feedback on the following:

  1. Is the code well structured? I notice I have a lot of redundancy. The search and delete methods are almost the same.

  2. I use a string to flag deleted keys until they are replaced, is there a better way to do this. Another boolean array maybe?

public class HashTable {
    //known limitation: This will break if the key value is set to none because I use none as the identifier string for deleted keys.
        private int capacity;
        String values();
        String keys();
        public HashTable(int capacity){
            this.capacity = capacity;
            values = new String(this.capacity);
            keys = new String(this.capacity);
        }

        public int hash(String key){
            int sum = 0;
            for (int i=0; i<key.length();i++){
                sum+=key.charAt(i);
            }
            return sum%capacity;
        }

        public void add(String key, String value){
            int keyhash;
            int i = 0;
            while(i!=capacity-1){
                keyhash = (hash(key)+i)%capacity;
                System.out.println("Try "+ i);
                if(values(keyhash)==null || values(keyhash).equals("none")) { //add delete flag to this condition after implementing delete.
                    values(keyhash) = value;
                    keys(keyhash) = key;
                    break;
                }

                if(values(keyhash)!=null && keys(keyhash).equals(key)){
                    values(keyhash)=value;
                    break;
                }
                i++;
            }
        if(i==capacity-1)
            System.out.println("Table appears to be full,unable to insert value");
        else
            System.out.println("Value inserted successfully.");
        }

        public String get(String key){
            int i = 0;
            int keyhash = (hash(key)+i)%capacity;
            while(values(keyhash)!=null && i<capacity){
                //System.out.println("Try " +i + " of finding the key.");
                if(keys(keyhash).equals(key))
                    return values(keyhash);
                i++;
                keyhash = (hash(key)+i)%capacity;
            }
        return null;
        }

        public void remove(String key){
            int i = 0;
            int keyhash = (hash(key)+i)%capacity;
            while(keys(keyhash)!=null && i<capacity) {
                if (keys(keyhash).equals(key)) {
                    keys(keyhash) = "none";
                    values(keyhash) = "none";
                    return;
                }
                i++;
                keyhash = (hash(key)+i)%capacity;
            }
            System.out.println("Key does not exist in table");
        }


        public void getHashedValues(){
            System.out.println();
            for(int i = 0; i<values.length;i++){
                System.out.print(" "+ values(i));
            }
            System.out.println();
        }


    }

hash map – Javascript object to be used as a key in a Map

I have a use-case where we need to use a javascript object as a key in a Map. If we don’t implement a toString() method we’re going to end up with (object Object) by default so i came up with the below pattern. Are there any drawbacks to this, or a better way to achieve this?

var Name = function(name) {
    this.name = name;
    this.id = Math.random().toString(36).slice(2);
}

Name.prototype.toString = function() {
    return this.id;
}

algorithm – How can I optimize this Hash function to get a perfect hash?

I have 27 words, I am trying to fit into 37 or less array indexes, and I get so damn close to getting a perfect hash, but there is always a couple that get in the way. It has to be a mathematical algorithm, no else/if or anything like that, but, what are some good ways I could help make this hash code perfect?

here is my hash code

while(i < hashTable.length - 1)
        {
                System.out.println((((int)hashTable(i).charAt(0) - 97 + hashTable(i).length()) % 3) + "tt"  + ((int)hashTable(i).charAt(hashTable(i).length() - 1) % 12));

           // System.out.println(i + ": " + hashTable(i) + ": t" + ar(i) + "tt" + (ar(i)/109));
            i++;
        }

here is my hash table

String hashTable() = {"a", "after", "all", "and", "because", "every", "for", "from", "had", 
                            "have", "in", "is", "it", "its", "now", "of", "on","so", 
                            "that", "the", "their", "there", "to", "was", "were", "which", "with", ""};

hash tables – Does making the keys of a hashtable the same length make the hashtable any better?

Thanks for contributing an answer to Computer Science Stack Exchange!

  • Please be sure to answer the question. Provide details and share your research!

But avoid

  • Asking for help, clarification, or responding to other answers.
  • Making statements based on opinion; back them up with references or personal experience.

Use MathJax to format equations. MathJax reference.

To learn more, see our tips on writing great answers.

opsec – Hash Identification – Sharing Information Security Stacks

Stack Exchange Network

The Stack Exchange network consists of 176 question and answer communities, including Stack Overflow, the largest and most trusted online community for developers to learn, share their insights, and develop their careers.

Visit Stack Exchange

Hash Tags Work :)

He lived in Los Angeles and was doing notary public work. At that time I created a fan page on Facebook. I made a lot of hash tags and to this day I still get 100 visits per day.

Anyway, I now have a new fan page for my freelance work / services. Does anyone know where I can find the hot hash tags that people are looking for?

hash – How to store the MFA secret

I have an online application that I am adding MFA to, using the Google / Microsoft Authenticator applications for mobile phones. I tried to take a security-centric approach to storing the MFA secret and right now that secret is being encrypted with the users password inside a database field. We do not store the password itself, but the password hash and use it to compare it with the password sent by users at runtime to compare.

Now I am realizing that there is a flaw in this methodology and that is when the user forgets his password and requests a password change. At that time, we have no way to decrypt the users secret (using their old password) so that we can re-store the secret using the new password sent.

I was wondering how others deal with this? In my opinion, we have the following options:

  1. We force the user to configure their mobile application again with a new secret
  2. We encrypt the secret, not to the user's password, but to another form using another encryption chain

I suppose (1) is the easiest but not the best for the user: they would have to delete their (old) app account before scanning a QR code (or equivalent) to set up a new account.

(2) I like the idea, but I wonder how we should do it. I thought of taking a hash of the users email address and using it as the encryption string as we can programmatically restore everything without the users password but am not sure it is secure enough?

Can anyone give me some guidance here on where to look for possible solutions?