Monday, 22 May 2023

FNV hash algorithm implementation in Java

 

FNV hash algorithms are designed to be fast while maintaining a low collision rate. The primary objective of FNV hashes is to achieve fast performance while minimizing the occurrence of collisions. As the FNV hashes exhibit a high level of dispersion, making them particularly effective for hashing similar strings like URLs, hostnames, filenames, text, and IP addresses. Their rapid processing speed enables efficient hashing of large volumes of data while still maintaining a reasonably low collision rate. However, it is important to note that FNV hashes are generally unsuitable for cryptographic purposes.

 

FNV hash algorithm is not suitable for cryptographic use

FNV hash algorithm is not suitable for cryptographic use due to several reasons.

 

a.   Predictable in nature: FNV hashes has a simple and predictable structure, whereas cryptographic hash functions must be highly unpredictable.

b.   Lack of security features: FNV hashes lack security features that are essential for cryptographic applications. They do not provide cryptographic properties like resistance to preimage attacks, collision resistance, second preimage attacks etc.,.

c.    Limited hash size: FNV hashes typically use a fixed or limited hash sizes, whereas Cryptographic hash functions often have larger hash sizes to increase the complexity of brute force attacks.

 

FNV hash algorithm benefits in non-cryptographic use cases

a.   Simple to implement: It is easy to implement as compared to cryptographic hash algorithms

b.   Faster calculations: FNV hash is designed to be fast, making them efficient for hashing large amounts of data quickly.

c.    Low collision rate

d.   Dispersion: FNV hash algorithm evenly distribute the hash values across the entire hash space.

 

Following implementation is a reference to the doc (https://datatracker.ietf.org/doc/html/draft-eastlake-fnv-17)

 


 

FnvHash.java 

package com.sample.app.util;

import java.math.BigInteger;

/**
 * Reference implementation:
 * https://tools.ietf.org/html/draft-eastlake-fnv-17#section-6
 */
public class FnvHash {
	private static final long FNV_64_BASIS = 0xcbf29ce484222325L;
	private static final long FNV_64_PRIME = 0x100000001b3L;

	private static final long FNV_32_BASIS = 0x811c9dc5;
	private static final long FNV_32_PRIME = 0x01000193;

	private static final BigInteger FNV_128_BASIS = new BigInteger("144066263297769815596495629667062367629");
	private static final BigInteger FNV_128_PRIME = new BigInteger("309485009821345068724781371");

	private static final BigInteger FNV_256_BASIS = new BigInteger(
			"100029257958052580907070968620625704837092796014241193945225284501741471925557");
	private static final BigInteger FNV_256_PRIME = new BigInteger(
			"374144419156711147060143317175368453031918731002211");

	private static final BigInteger FNV_512_BASIS = new BigInteger(
			"9659303129496669498009435400716310466090418745672637896108374329434462657994582932197716438449813051892206539805784495328239340083876191928701583869517785");
	private static final BigInteger FNV_512_PRIME = new BigInteger(
			"35835915874844867368919076489095108449946327955754392558399825615420669938882575126094039892345713852759");

	private static final BigInteger FNV_1024_BASIS = new BigInteger(
			"14197795064947621068722070641403218320880622795441933960878474914617582723252296732303717722150864096521202355549365628174669108571814760471015076148029755969804077320157692458563003215304957150157403644460363550505412711285966361610267868082893823963790439336411086884584107735010676915");
	private static final BigInteger FNV_1024_PRIME = new BigInteger(
			"5016456510113118655434598811035278955030765345404790744303017523831112055108147451509157692220295382716162651878526895249385292291816524375083746691371804094271873160484737966720260389217684476157468082573");

	private FnvHash() {
	}

	private static long hash(byte[] data, long basis, long prime) {
		long hash = basis;

		for (int i = 0; i < data.length; ++i) {
			byte dataByte = data[i];
			hash ^= dataByte;
			hash *= prime;
		}

		return hash;
	}

	private static BigInteger hash(byte[] data, BigInteger basis, BigInteger prime) {
		BigInteger hash = new BigInteger(basis.toString());

		for (int i = 0; i < data.length; ++i) {
			byte dataByte = data[i];
			byte[] byteArray = { dataByte };
			BigInteger dataByteBigInteger = new BigInteger(byteArray);

			hash = hash.xor(dataByteBigInteger);
			hash = hash.multiply(prime);
		}

		return hash;
	}

	public static long hash32(byte[] data) {
		return hash(data, FNV_32_BASIS, FNV_32_PRIME);
	}

	public static long hash64(byte[] data) {
		return hash(data, FNV_64_BASIS, FNV_64_PRIME);
	}

	public static BigInteger hash128(byte[] data) {
		return hash(data, FNV_128_BASIS, FNV_128_PRIME);
	}

	public static BigInteger hash256(byte[] data) {
		return hash(data, FNV_256_BASIS, FNV_256_PRIME);
	}

	public static BigInteger hash512(byte[] data) {
		return hash(data, FNV_512_BASIS, FNV_512_PRIME);
	}

	public static BigInteger hash1024(byte[] data) {
		return hash(data, FNV_1024_BASIS, FNV_1024_PRIME);
	}
}

 

FnvHashDemo.java

package com.sample.app;

import com.sample.app.util.FnvHash;

public class FnvHashDemo {

	public static void main(String[] args) {
		byte[] data = "Hello World".getBytes();

		System.out.println("hash32 : " + FnvHash.hash32(data));
		System.out.println("hash64 : " + FnvHash.hash64(data));
		System.out.println("hash128 : " + FnvHash.hash128(data));
		System.out.println("hash256 : " + FnvHash.hash256(data));
		System.out.println("hash512 : " + FnvHash.hash512(data));
		System.out.println("hash1024 : " + FnvHash.hash1024(data));

	}

}

 

Output

hash32 : -5336392468792335065
hash64 : 4420528118743043111
hash128 : 359416569417164191184508690843380606405809832223028314225101296326512917370623229481933722410143532816993268364815906017493350815888975405026594832106527628279593938783372633309959136690420772822604590612174209472863509067085307500686780392967231258276262735055947936280657998082761259208397437248493339648470263098936644959894391
hash256 : 2011680629684634206990388480190090435343680968147577606510118098785136616842295581768126817706848957483666175907049484298199761898007425591922717758749771349072663183918762548014159568920483936348201725773617681691705401788854521058614316590534670296327479621526501946025673881035897907188763891369361321634014701636891261324342354862188029263921189712915724130263123819226504993413400877783651229898980916427946228882421168769880018658096404528464164684181500796118215567216895347012990626315456760427452165215836439555027072575044858926692388027919536028566603820720141024462447727450479359892551003065764765629370686939481782355495
hash512 : 1209064271914848759749895219962958656694173178575401915154704877409794588970155437417952170649898566732541447825707820233329427420749059125532212172856797398471676641808899434049991789700394708105783912597931617426929424895323346729237640572522814298409453732610622953738746152695475814090516834954427001340403107589353348402570278598195312660543873965645563750370865110171494611809582691923666248844009294559179451841594180275249274071275142321406136223735672859682456535383207878181314649933157624926385270784432555438401721610672643494393855056429240946731932909335662532741092005640282306913366045458097922467821365664725736574604068621489618707955433711055142114209723824819178429402771820289436485608678560772059917271505379379270804907619258034208600946360759075927156081243287423049410593338633171380080445030556376717493984619406399702640307617115219450935394631179544440685306509810182059196280905985688580404848667477045224208198656238736446058625028175280958664806090663802623465407416263909210756776223931204126531067284421843587057560650619600008998132233141202628701217834580045350976365195325649803705231461173472583226421025253957827765443850675603765486752149080488115827466587365229019658217030551285364570396280834881707297968011981652760462280504433601412472916784236286799
hash1024 : 718767562950373817771769638192123090298641071048602067445849806452566640373161690182600926305940550380616136164349688166482231826476335106393149835382803117379858841795397097239167295705736455050719178312572401769437716489772894089672214198853003475031376926772206814668848827613033240357268449613350193544443026978131742746171311739245154967451127957891476264414691547521281305294482950285192850817099640022906129642851381375963247268810622344994365300572310800233645880133943086367340971770815794897223390794265316631248012275246371255975541849283025494735727515086121347894271644913380628401320407382142862564442049984458209956989714090786298693416456464705477282382731529256962526297901317782302577179321393588161825352611163377763323754695707585281198057698321008625278006914072427340180856335607748594806800354825079091688747499553332819663746626696401217723401470131441928356311480242570122935458078267694478885380848058621247967692195639065941122519049090140256113570655373912324431847753614723856697983228691945272237911676052032429937265315909823695130748719723507225232748286272882844590290054354518670875589886457073276525291124132101400496175737706661556143358479595475258353915613199758057069328996310141982611375892671927039369839833641317008244000587898306721005446295079576394384182667220374022214599120948460933627871828073056909856914528947698297394146586260133975652832144522338468222774477255095557948732407525030083750544437823596912232662113530138389106013812865394058593850820160463056963476803993485908368318274743684438535034174817520673612404784787233982249028584086635959966300607075690474393623584633535972555268638671769617814761387340598664652082871046708057713300997378218450670036305033187056328835404719306587667208072624884093702188387816303528566227747934062372648761515796369869087546722121945346425787215046714174447413435183590346057271846080731800723392085133931687359892308034007597714082640366313780458113886607790775371191740030131640211648479360632314576503896961731230038381416104296343328009357565035463693270530987397292427304512158751853902493728321028598215639421460707488668416409557360487303804220974808492732618066046113714116793592173998910415762595429804238316392154648358868054872525028983592789149485781387261795213663502046318372249871419861653386535990230794794617873948759786172913080036601587383344622401308947360454054407694666127817193392193531541356391411262199908981873304448038223062646741435273488272784506248863059163309909484858372781539948543301264928344125792115133423

 

References

https://datatracker.ietf.org/doc/html/draft-eastlake-fnv-17

  


 

You may like

Interview Questions

Scanner throws java.util.NoSuchElementException while reading the input

How to get all the enum values in Java?

Extend the thread to check it’s running status

Implement retry handler for a task in Java

Design an utility class to capture application metrics summary in Java

Utility class to get primitive type from wrapper type and vice versa

No comments:

Post a Comment