Hash function, hash table lecture notes study

Feb. 6, 2017

3 lecture notes to study 

Spent more than 2 hours to study the lecture notes - Lecture 6 about Rabin-Karp algorithm from MIT, and also lecture 7, resize of hashtable. 

Will come back to write down some notes and also share something about the algorithm.

Lecture 5 notes: 

Hash functions

Consider a function h(k) that maps the universe U of keys (specific to the hash table, keys could be integers, strings, etc. depending on the hash table) to some index 0 to m. 
We call this function a hash function. 

A good hash function

. satisfies ( approximately) the assumption of simple uniform hashing: each key is equally likely to hash to any of the m slots. The hash function shouldn't bias towards particular slots

. does not hash similar keys to the same slot (e.g. compiler's symbol table shouldn't hash variables i and j to the same slot since they are used in conjunction a lot)

. is quick to calculate, should have O(1) run time

. is deterministic. h(k) should always return the same value for a given k

Example 1: Division method 

prime number vs should ok be a power of 2 

h(k) = k mod m 

if m = 2 ^p, then the h(k) only looks at the p lower bits of k, completely ignoring the rest of bits in k. A good choice for m with the division method is a prime number ( why are composite numbers bad?). 

Example 2: Multiplication method


h(k) = floor(m(k A mod 1))

Collisions

Chaining - 

load factor alpha

If there are n keys in a hash table with m slots, we can the load factor alpha for the hash table to be n/m. 
Under the assumption of simple uniform hashing, the length of each linked list in the hash table is alpha. 

Open addressing collisions 


Linear probing 

Linear probing resolves collisions by simply checking the next slot, i.e. if a collision occurred in slot j, the next slot to check would be slot j + 1. More formally, linear probing uses the hash function 

  h(k, i) = (h'(k) + i ) mod m. 

Quadratic probing resolves collisions in a similar fashion: 

h(k, i) = h'(k) + c₁ i + c₂ i²) mod m

for some constants c₁, c₂. Instead of linearly traversing through the hash table slots in the case of collisions, quadratic probing introduces more spacing between the slots we try in case of a collision, which reduces the clustering effect seen in linear probing. 

Double hashing resolves collisions by using another hashing function to determine which slot to try next. 

Lecture 6 notes 

Rabin-Karp algorithm

probe sequence  

Performance of Open Addressing

linear probing 
quadratic probing 
double hashing 

simple uniform hashing assumption (SUHA)
a hash function mapped to any slot from 0 to m -1 with equal probability 

uniform hashing assumption (UHA) 
a random permutation of the slots 0 to m-1 

load balance alpha, p = 1 - alpha probability that the first probe will find an empty slot under UHA. 

Universal hashing  

Rolling hash 

Lecture 7 notes

Hash table

Learn a few keywords:

probe sequence  

Performance of Open Addressing

linear probing 
quadratic probing 
double hashing 

simple uniform hashing assumption (SUHA)
a hash function mapped to any slot from 0 to m -1 with equal probability 

uniform hashing assumption (UHA) 
a random permutation of the slots 0 to m-1 

load balance alpha, p = 1 - alpha probability that the first probe will find an empty slot under UHA. 

Universal hashing  

Hackerearth "January Easy '17 contest" Simple Function

January 1, 2017

Plan to attend 8:00 - 11:00am hackerearth.com

January Easy '17 contest

Work on the algorithm:

January Clash '2017


- One of 6 algorithms: Simple Function

In contest performance, C# solution, pass test case 1, but timeout all other cases. (9:00am - 11:00am)

C# solution, passed 5 test cases, fail last one. (after the contest, 2+ hours)

Study code C++

Write C# code using the above solution. (Time spent: 4 + hours, completed at 6:37pm)

Code Review Link is here. Julia spent more than one hour on January 3, 2016 to add her calculation of cache size reduction from 2MB to 80KB based on the comment from Paparazzi


January 7, 2016
Continue to do some research on C# Dictionary comparison to self-defined hash function to do pre-processing.

Using Dictionary<string, int>

C# with Dictionary code:

Test result from hackerearth.com:

The time complexity analysis:
function CalculateSumOfEvenNumbers(), inside two loops, function GetLastDigit(...)
is called; inside GetLastDigit() function, there is a HashSet to prevent
duplicate calculation, and then, GetLastDigit() is called; inside GetLastDigit(),
two calls of the function GetDigits(). Actually, we only care about two integer
number, biggest same digit, and we do not care about how many digit inside
each integer. And this approach goes over each digit in the integer.



Self-defined hash function

Comparison to the self-defined hash function - code is here:
The performance:

Time analysis:

For each query, process two baskets of integers,  two separate loops, O(N1 + N2), detail see function ProcessInput(...); For each number, call Hash function to process, any number is at most 4 digits, each digit, only do one calculation to determine the digit from 1 to 9. Just a minus arithmetic calculation. Detail see the function Hash(char[] cache, int nthNumber, int serialNo)

To calculate the even number count, call function CheckNumberIsEven(...) N1 * N2 times, each function call, only need to look up at most 10 times, find a match then break the loop.

So, overall, time complexity is O(N1+N2) + O( N1*N2), is around O(10^6) calculation of CheckNumberIsEven function which includes a few of arithmetic calculations; the self-defined hash function is almost less than 1 percent of time to compare calculation the even number count.

Digits Internal Class

Another C# version, no Dictionary, just use int[10] to store an integer, with digits. No string manipulation to get the substring. Pass all test cases. Code is here.

Performance:

HashedInteger Class

Digits class name is not very meaningful, so HashedInteger class name is chosen to replace Digits.
And also Save API is not clear, add Convert, ConvertAll APIs instead.

The code is here.

Security Checklist for PHP Web Applications

Here is the article. 

In Brief

The below is a short checklist outlining the most common vulnerabilities of web applications and applicable PHP solutions and best practices. Although focused on PHP, this checklist can be extended to all programming languages.

Validation of Inputs

Advice:

• during development the configuration error_reporting = E_ALL (without removing the E_NOTICE) is used to recognise uninitialised variables; in production, errors should not be displayed in the web interface;
• filter_var () and filter_input () statements are very useful for filtering and validating inputs;
• the use of content equality and === type avoids errors during comparison with Booleans. The expression (0 == false) is true while (0 === false) is false;
• casting can be faster than testing (compare the is_numeric function to a (int) $value type conversion);
• beware of the $_REQUEST global super variable because it may contain values from many different sources;
• check for different inputs using isset, for example isset ($ _ GET ['id']);
• also pay attention to some fields in $_SERVER such as $_SERVER ['HTTP_REFERER'];
• as we cannot trust browsers, pass $_FILES ['file'] ['name'] through the basename function when uploading files; (imagine $_FILES ['file'] ['name'] = '../../../etc/passwd')
• check the content of uploaded files. Images must be checked with the getimagesize() function, which returns false when the file is not of this type. Think also about the fileinfo extension;
• do not accept serialised objects as input.

In general, it is advisable to use the concept of a whitelist for many cases of validation.

An extra layer of protection or protection of an already existing application can be provided by adding “PHP Input Filter” and “PHPIDS” or “mod_security” if you use Apache

SQL Injection

Using raw SQL queries by concatenating variables to the query string is bad practice that can easily lead to unwanted SQL injection.

Advice:

• Use prepared statements. In PHP the easiest way to handle escaping variables is to use an abstraction layer such as PDO.
• Parameterised queries are also accessible for some databases through basic PHP functions (e.g. postgresql or pg_prepare) or with extended libraries such as mysqli.
• If concatenation cannot be avoided, it is imperative to escape the variables using functions of the type “(real_) escape_string”. For mysql, for example, find out about the mysql_real_escape_string function. It is useful to add that the PHP manual advises against using this function, but it can be useful for quick securing of an old application.
• Avoid at all costs automatic techniques such as magic_quotes and/or generic add_slashes. Each database will react differently to these escape methods.

Cross-Site Scripting (XSS)

Consists of the use of javascript as input to be executed during display. This is a very common and dangerous vulnerability, although it is easy to avoid in many cases. You will find a fairly complete list of possible attacks on the OWASP website.

• transform all characters of displayed variables into html entities. In PHP it is therefore often enough to pass all the variables displayed by the htmlentities function. Some “templating systems” such as “flexy” make an automatic escape;
• if you need to pass HTML in the variables, the strip_tags function can be used to filter permitted tags. However, this function is dangerous because of the javascript injection in the permitted arguments; e.g.: <img onmouseover="alert(‘XSS’);" src="" /> or <a href="javascript:alert(‘XSS’);">link</a>. It is, therefore, usually necessary to create your own filter function in addition to strip_tags;
• a good way to filter html is the “html purifier” class (http://htmlpurifier.org/, LGPL license).

In general, a generic display function must be written and used during any display.

Code Injection

Injection of malicious code that will be executed by the application.

• avoid using variables in the include or require instructions. If it cannot be avoided, the use of whitelist filters is important;
• avoid the “eval” instruction at all costs or treat it with the utmost care; (alternatives (http://www.php.net/manual/de/language.variables.variable.php), closures (http://www.php.net/manual/de/functions.anonymous.php) and the call_user_func()) function
• in php.ini, set allow_url_fopen to off if the function is not required.
• avoid variables in preg_replace type functions.

Injection of Instructions

Some functions can be used to run system instructions.

• avoid variables in instructions such as shell_exec, exec, system, passthru, popen;
• if they cannot be avoided, the escapeshellarg() and escapeshellcmd() functions must be used;
• use whitelists and the basename function in filenames.

Session Security

By stealing the session identifier, other users’ sessions can be used. See “firesheep”, for example.

• avoid using the session identifier in the URL because another site could steal the identifier by checking the “referer” or might even set your session identifier (imagine a link to a site such as link?PHPSESSID=123). So set use_only_cookies to 1 or On in php.ini;
• only use SSL (TLS) communications, otherwise the session cookie may be intercepted on hostile networks. Require the session cookie to be communicated only in SSL: session.cookie_secure=1;
• set an expiration time for sessions
• associate visitor IP addresses with their sessions.

Cross-Site Request Forgery (XSRF)

Involves the use of the open session in another browser tab by a malicious web page. Most often the vulnerable parts will be forms, which could be completed by a malicious site. In this case it is easy to avoid this type of attack by creating a unique identifier for the form and checking it during form submission. It is good practice to use a nonce created by a function such as uniqid or pseudo random hash with a secret code by using the hash_hmac function, which is placed in a hidden field on the form and in session, to be checked during submission.

To protect non-form functionalities, case-by-case analysis is required.

Best Practices for Storing User Passwords in the Database

Passwords must be stored in the database in hashed form. To do this, it is important, above all, not to use md5 or sha1 type algorithms, for which there are “rainbow tables”, which can be used to obtain the password quickly from the hash.

In addition, specifically to avoid the use of rainbow tables, and to hide identical hashes from the same password, it is important to use a salt. This salt will be determined randomly and concatenated to the password before hashing. The salt and the hash will therefore be stored in the database.

It is also important to add a secret salt constant that would be stored somewhere other than in the database, for example in a configuration file.

The use of a concatenated salt can be usefully replaced by a hash_hmac hash function, but we recommend the use of the crypt function (http://php.net/manual/en/function.crypt.php) which enables a cost factor to be added to the calculation when using CRYPT_BLOWFISH, CRYPT_SHA256 or CRYPT_SHA512 (see key stretching).

The hash calculation will then have the following form, for example:

$hash=crypt(hash_hmac('sha512','secret password',$saltsecretconfig), '$2y$’.$cost.'$randomsaltDB$') ;

The variable $cost will need to be set to a number such that the duration of the operation is viable for your application, but prohibitive for a brute-force attack (1/100 seconds for example).

PHP 5.5 introduces new hash functions that enable secure storage of passwords (see http://www.php.net/manual/en/function.password-hash.php).

The function above becomes:

$hash = password_hash(hash_hmac(‘sha512’, ‘secret password’, $saltsecretconfig), PASSWORD_BCRYPT, ['cost'=>$cost]); // from PHP 5.5

Use of Countermeasures

In general, a web application will be scanned with an automatic tool by an attacker before compromise. It is therefore possible to place cyber traps or other “tar pits” on the application. A practical example called “weblabyrinth” can be downloaded from http://www.mayhemiclabs.com/content/new-tool-weblabyrinth. But useless scripts containing “sleep” functions or other false authentications can already perform this function.

Webroot! = Approot

Placing libraries and other scripts in places that cannot be accessed directly from the Internet is a definite advantage. It means that libraries with vulnerabilities cannot be exploited directly.

Denial of Service

It is not possible to defend entirely against denial of service type attacks. However, it is possible to optimise applications so that they respond better. Although this is beyond the scope of this document, the following are some concepts that can be explored:

• use “foreach” only for associative arrays and generally avoid any unbounded iteration on data from databases;
• use a compiled code cache engine (memcache, eaccelerator, Zend Platform, …);
• some debugging tools can report bottlenecks to you (xdebug, yslow, firebug, …)
• compress your javascript;
• check for slow queries (mysql_slow_query);
• possibly compress server-client communication (only for heavy traffic and where the server CPU is sufficiently powerful);
• if you use Apache consider using the mod_evasion module.

Frameworks

Many frameworks are written by experienced developers and benefit from their extensive security experience and good programming practices. They often, therefore, include many of the techniques outlined above and enable web applications to be developed more quickly and securely. Examples: Zend, Symfony…

Advice for php.ini

The open_basedir configuration function is used to define the directories to which the application has access and therefore offers higher security.

The following php.ini parameters should be set to the needs of your application while trying to keep them as low as possible. In general it is advantageous to set these parameters on the fly with ini_set in scripts that need more resources than the bulk of the application:

• max_execution_time
• memory_limit
• post_max_size
• upload_max_filesize

Check this value in the production environment:

• display_errors = Off

1044. Longest Duplicate Substring | Hard level | Binary search + Rabin Carp hash

 Given a string s, consider all duplicated substrings: (contiguous) substrings of s that occur 2 or more times. The occurrences may overlap.

Return any duplicated substring that has the longest possible length. If s does not have a duplicated substring, the answer is "".

Approach 1: Binary Search + Rabin-Karp

String Searching Algorithms

The problem is a follow-up of Longest Repeating Substring,
and typically used to check if you're comfortable with
string searching algortihms.

Best algorithms have a linear execution time on average.
The most popular ones are
Aho-Corasick,
KMP and
Rabin-Karp:
Aho-Corasick is used by fgrep,
KMP is used for chinese string searching,
and Rabin-Karp is used for plagiarism detection and in bioinformatics to look for similarities in two
or more proteins.

The first two are optimized for a single pattern search,
and Rabin-Karp for a multiple pattern search,
that is exactly the case here.

Split into two subtasks

Here we have a "two in one" problem:

1. Perform a search by a substring length in the interval from 1 to N.

2. Check if there is a duplicate substring of a given length L.

The linear time implementation of this idea is a bit
tricky because of two technical problems:

1. How to implement a string slice in a constant time?

2. Hashset memory consumption could be huge for very long strings.
   One could keep the string hash instead of string itself
   but hash generation costs $O(L)$ for the string of length L,
   and the complexity of the algorithm would be $O((N-L)L)$,
   N - L for the slice and L for the hash generation.
   Therefore, we should think about how to generate a hash in a constant time.

Let's now address these problems.

String slice in a constant time

That's a very language-dependent problem. For the moment for
Java and Python there is no straightforward solution,
and to move sliding window in a constant time
one has to convert string to another data structure.

Python is already providing memoryview,
which is known to be surprisingly slow,
and there is a lot of discussion about strview.

The simplest solution both for Java and Python is to convert string to integer array of ascii-values.

Rolling hash: hash generation in a constant time

To generate hash of array of length L, one needs $O(L)$ time.

How to have constant time of hash generation? Use the advantage of
slice: only one integer in, and only one - out.

That's the idea of rolling hash.
Here we'll implement the simplest one, polynomial rolling hash.
Beware that's polynomial rolling hash is NOT the Rabin fingerprint.

Since one deals here with lowercase English letters, all values
in the integer array are between 0 and 25:

arr[i] = (int)S.charAt(i) - (int)'a'

So one could consider string abcd -> [0, 1, 2, 3] as a number
in a numeral system with the base 26.
Hence abcd -> [0, 1, 2, 3] could be hashed as

$h_0=0\times 26^3+1\times 26^2+2\times 26^1+3\times 26^0$

Let's write the same formula in a generalized way, where $c_i$
is an integer array element and $a=26$ is a system base.

$h_0=c_0{a}^{L-1}+c_1{a}^{L-2}+...+c_i{a}^{L-1-i}+...+c_{L-1}{a}^1+c_L{a}^0$

$h_0={\sum }_{i=0}^{L-1}{c}_i{a}^{L-1-i}$

Now let's consider the slice abcd -> bcde. For int arrays that means
[0, 1, 2, 3] -> [1, 2, 3, 4], to remove number 0 and to add number 4.

$h_1=(h_0-0\times 26^3)\times 26+4\times 26^0$

Let's look at what changed piece by piece. First, we subtracted $0\times 26^3$ from $h_0$; this removed the contribution of the first element in the array from the hash. Then we multiplied the remaining hash value by $26$, which increased the power of the base value for each of the elements remaining in the array (i.e., $2\times 26^1)\times 26=2\times 26^2$). Finally, we add the contribution of the new element (e) to the hash. This results in:

$h_1=1\times 26^3+2\times 26^2+3\times 26^1+4\times 26^0$

Thus after applying a constant amount of operations to the hash for abcd, we have obtained the hash for the next substring, bcde.

In general form:

$h_1=(h_{0}a-c_0{a}^L)+c_{L+1}$

Now hash regeneration is perfect and fits in a constant time.
There is one more issue to address: the possible overflow problem.

How to avoid overflow:

$a^L$ could be a large number and hence
the idea is to set limits to avoid the overflow.
To set limits means to limit a hash by a modulus
and instead of using the hash itself, we will use h % modulus.

We should select a modulus that is large enough for our purpose, but how
large is that? You can read more about the topic here.

We must use caution when using a rolling hash to assess the equality of two substrings. The modulus can be thought of as the number of bins that we will use to store the starting index of seen substrings. So there is a higher probability of having two different substrings being stored in the same bin (h % modulus) when the modulus is small.

When two different strings have the same hash value, we call this a collision. In an ideal setting, where every test case is known, this issue could be resolved by adjusting the modulus to avoid collisions. However, in a real-world setting, whenever two substrings have the same hash, we must verify that the substrings are truly equal. This leads to a Rabin-Karp time complexity of $O(L(N-L))$ in the worst case, when many substring hashes collide.

Fortunately, we can reduce the probability of collisions by selecting a good value for our modulus.

Generally speaking, a good modulus will have two traits:

1. The modulus is not too big and not too small. That is to say, it is large, which helps reduce the probability of collisions, but it is still small enough to fit in a 32-bit integer.
2. It is prime. This helps increase the uniformity of our hash values after taking h % modulus, which in turn decreases the probability of collisions occurring. If you would like to know more about why this is, you can read about it here.

Here, we will use our favorite modulus, $10^9+7$, which satisfies both of these conditions.

One last note, there is another overflow issue here that is purely Java-related.
While in Python, the hash regeneration goes perfectly fine,
in Java, the same thing is better to rewrite to avoid
long overflow. Check here
the nice explanation by @hqt.

Binary search algorithm

• Use binary search by a substring length to check lengths from 1 to N
  left = 1, right = N. While left != right:

  • L = left + (right - left) / 2

  • If search(L) != -1 (i.e. there is a duplicate substring), left = L + 1

  • Otherwise (no duplicate substring), right = L.

• Return a duplicate string of length left - 1, or an empty string if
  there is no such a string.

Rabin-Karp algorithm

• Compute the hash of the substring consisting of the first L characters of string S.

• We will initialize the hash map of already seen substrings with this hash value as a key and a list containing the starting index of the substring (0) as the value.

  The reason we store the first index of the substring is so that if we see this hash value again, we can compare the current substring to each substring that has the same hash value to see if the two strings actually match or if this is a hash collision.

  Every time we compare two strings will cost $O(L)$ time. If we designed a very poor hash function or picked a very weak modulus value (like 1), we could potentially spend $O(L\cdot (N-L{)}^2)$ time comparing each substring of length L to all previous substrings of length L on each call to search.

  Fortunately, the hash function we are using guarantees that there will not be any collisions between hash values that are less than MOD (before taking the modulus). Furthermore, selecting a large, prime modulus helps create a more uniform distribution of the hash values that are greater than MOD. So the probability of two hash values colliding is very small, and on average, we expect the number of collisions to be negligible. Therefore, we can expect the search function to take $O(N)$ time on average.

• Iterate over the start position of each substring in S from $1$ to $N-L$. Note we already initialized our hashmap with the substring starting at index zero.

  • Compute the rolling hash based on the previous hash value.

  • If the hash is in t