[DopeTales] Pairing Functions 
Tags: hashingcppmath
Published: 2019-04-11 05:55:41

--- 
title: [DopeTales] Pairing Functions 
published: true
description: 
tags: Hashing Cpp math
---


Pairing functions are surprisingly useful increasing  application performace.
As per Wiki, Pairing functions  uniquely encode two natural numbers into a single natural number. 
While designing system software this feature can be exploited to reduce runtime data structures data footprint.

Here is Dope-tale about one of that use.
While design of compiler diagnostics or run time err0r checkers, we record error location at <line:column> 
pair from user code, typical implementation for this use-case is

~~~~
typedef std::uint32_t                             Line
typedef std::uint32_t                             Column
typedef std::pair<Line,Column>                    Location;
typedef std::map<Line,Location>		          LocationTable; 
// OR
typedef std::multi_map<Line,Location>		  LocationTable1;

~~~~

This implemenation creates wrong semantics. map implemenation does not cover multiple errors on same location.
While both of them fail in semantics as Line does not uniquely identify error and its location.

So we define problem as

 0 <= Line <= 2^32-1
 0 <= Column <= 2^32-1
 
Given \< Line,Column \>  --uniquely--\> Error, We would be needing O(1) search
with single key, like...
~~~~
typedef std::unordered_map \< LocationHash,ErrorDescriptor \> LocationTable;

~~~~

So we wish to pair two integeres into one. hence pairing functions. 
A pairing function is a *computable bijection*
    π : N × N → N . 
*  Line and Column are *natural number*
*  Practically 32 bits are enough to accommodate Line and Number
*  Key made by both can be accommodated in 64 bits


here is sample implemenation

~~~~
typedef std::uint32_t  UI32;
typedef std::uint64_t  UI64;
typedef std::uint64_t  Key64;
typedef std::uint32_t  LocationKey;
using LocationHash  = Key64;
typedef std::pair<LocationHash,ErrorDescriptor> LocationListItemPair;


struct PairHashFunction : std::binary_function<UI32,UI32,Key64>
{
	Key64 operator()(UI32 first,UI32 second) const{
		Key64 first64 = (Key64) first;
		Key64 second64 = (Key64) second;
		Key64 sum64 = (first64 + second64);
		Key64 hashValue64 = sum64 * (sum64 + 1) >> 1;
		return hashValue64 + second64;
	}
};

template<typename HashKeyType,typename KeyType>
struct UnPairHashFunctionTemplate
{
	void operator() (HashKeyType hashValue,KeyType *first, KeyType * second){
		HashKeyType temp =  (hashValue << 3)  + 1;
		temp  =  std::sqrt(temp) - 1;
		temp  =  std::floor(temp>>1);
		HashKeyType consum =  (temp * temp  + temp) >> 1;
		*second =  hashValue -  consum;
		*first  =  temp - *second;
	}
};

typedef UnPairHashFunctionTemplate<Key64,UI32> UnPairHashFunction;

class HitTable{
	LocationTable table;
public:
	void hit(Location locKey){
		PairHashFunction hfunc;
		Key64 key = hfunc(locKey.first,locKey.second);
		auto it =  table.find(key);
		if(it == table.end()){
			table[key] = 1;
		}
		else{
			KeyCountType count  = table[key];
			table[key] = count+1;
		}
	}

	bool isHit(Location locKey){
		PairHashFunction hfunc;
		auto it =  table.find(hfunc(locKey.first,locKey.second));
		return (it ==  table.end()) ? false :true;
	}
};

~~~~

HTH!