Collections Hashmaps vergleichen

[XPrototypeX]

Hey,
wie der Name schon sagt, will ich 2 Hashmaps vergleichen. Wenn in beiden Maps der selbe key mit dem selben value existiert, will ich diese Ausgeben. Dazu habe ich jetzt mal 2 Methoden geschrieben:

public void searchForSameData(HashMap<?, ?> map1, HashMap<?, ?> map2) {
		for (Entry<?, ?> getData : map1.entrySet()) {
			if (map2.containsKey(getData.getKey())) {
				if (map2.containsValue(getData.getValue())) {
					System.out.println(getData.getKey() + " "
							+ getData.getValue());

				}
			}
		}
	}

und

public void searchForSameData2(HashMap<?, ?> map1, HashMap<?, ?> map2) {
		for (Entry<?, ?> data : map1.entrySet()) {
			if (map1.get(data.getKey().hashCode()) == map2.get(data
					.getKey().hashCode())) {
				if (map1.get(data.getValue().hashCode()) == map2.get(data
						.getValue().hashCode())) {
					System.out.println(data.getKey() + " " + data.getValue());
				}
			}
		}
	}

Nun bei dieser Methode stimmt irgendetwas nicht. Er gibt mir einfach die komplette HashlMap aus (wahrscheinlich habe ich die Methode get() nicht richtig verstanden^^).

Bei der ersten Methode hab ich außerdem noch eine Frage: Wie funktioniert die Methode contains? Wenn ich zum Beispiel ein Byte Array habe, gibt die Funktion true zurück, wenn beide Hashmaps je die selben Byte arrays mit den selben Werten beinhaltet?

 

[Marco13]

Nun bei dieser Methode stimmt irgendetwas nicht. Er gibt mir einfach die komplette HashlMap aus (wahrscheinlich habe ich die Methode get() nicht richtig verstanden^^).

Oder die HashMap selbst. Der hashCode IST nicht der Key. (Es wird nur intern der hashCode des Objektes verwendet, das als Key fungiert). Sowas wie

public void searchForSameData(HashMap<?, ?> map1, HashMap<?, ?> map2) {
        for (Entry<?, ?> getData : map1.entrySet()) {
            if (map2.entrySet().contains(getData)) ...
        }
    }

sollte glaub' ich auch gehen. Abgesehen davon: Nicht
public void searchForSameData(HashMap<?, ?> map1, HashMap<?, ?> map2) {
sondern
public void searchForSameData(Map<?, ?> map1, Map<?, ?> map2) {
schreiben, das ist allgemeingültiger.

Bei der ersten Methode hab ich außerdem noch eine Frage: Wie funktioniert die Methode contains? Wenn ich zum Beispiel ein Byte Array habe, gibt die Funktion true zurück, wenn beide Hashmaps je die selben Byte arrays mit den selben Werten beinhaltet?

Bzgl. containsKey oder containsValue? Egal, die Antwort ist: Ja. Allerdrings solltest du beachten, dass sie NICHT true zurückliefert, wenn es nur die gleichen (aber nicht dieselben) Byte arrays sind.

 

[XPrototypeX]

Also meinst du das so:

public void test(){
		HashMap<byte[], byte[]> map1 = new HashMap<>();
		HashMap<byte[], byte[]> map2 = new HashMap<>();
		byte[] a1 = {0,1,2,3,4,5};
		byte[] a2 = {0,1,2,3,4,5};
		
		map1.put(a2, a2);
		
		map2.put(a2, a2);
		
		//cointains liefert true
		
		map1.put(a2, a2);
		
		map2.put(a1, a1);
		
		//containes liefert false
		
		
	}

Jedenfalls danke schon mal.

Kleiner edit. Ich will ja explizit die Hashcodes miteinander vergleichen. Damit ich bei so was wie oben angegeben schauen kann ob vielleicht die 2 Byte Arrays die selben Daten beinhalten. Da der Hashcode von a1 und a2 theoretisch gleich sein sollten.

 

[Marco13]

Ja, das mit dem hashCode funktioniert eben so nicht. Und die hashCodes der beiden Arrays müßten NICHT gleich sein (der hashCode eines Arrays hängt nicht vom Inhalt ab)

 

[XPrototypeX]

Hammm... Dann wäre es eigentlich besser gleich mit Strings zu arbeiten. Saugt zwar an der Performance jedoch müsste ich ja dann nicht immer beide byte Arrays auf ihre Gleichheit hin kontrollieren.

 

[Spacerat]

Ahhh... vergleichen vom Maps... da kann mir evtl. mal jemand den Gefallen tun und meine Toolkit-Methoden ein wenig ausgiebiger testen... die hab' ich vor langer Zeit mal implementiert, weil ich annahm, ich würde sie häufiger benötigen, aber naja... hält sich in Grenzen .

	public static <K, E> boolean equals(Map<K, E> a, Object b) {
		return (b instanceof Map) ? equals(a.entrySet(),
				((Map<?, ?>) b).entrySet()) : false;
	}

	public static <A> boolean equals(Collection<A> a, Object b) {
		if (a == b) {
			return true;
		}
		if (a != null && b instanceof Collection) {
			boolean rc = a.size() == ((Collection<?>) b).size();
			Iterator<A> aa = a.iterator();
			Iterator<?> bb = ((Collection<?>) b).iterator();
			A aaa;
			Object bbb;
			while (rc && aa.hasNext()) {
				aaa = aa.next();
				bbb = bb.next();
				rc &= aaa == bbb || (aaa != null && aaa.equals(bbb));
			}
		}
		return a == null && b == null;
	}

BTW.: Für den Hash eines Arrays hat's in der java.util.Arrays-Klasse einige Methoden. Für die Hashes primitiver Arrays tuts auch "ByteBuffer.wrap(myByteArray).hashCode()" (exemplarisch für Bytearrays). Vergleichen primitiver Arrays dann analog dazu "BytBuffer.wrap(byteArrayA).equals(ByteBuffer.wrap(byteArrayB)" (ebenfalls exemplarisch für Bytearrays).

 

[XPrototypeX]

Sooo. Danke. Jedoch muss meine Methode perfomant sein, da Maps mit ca. 700.000 - 2.000.000 Einträgen überprüft werden müssen.

Ich hab jetzt nochmal was kleines gebaut und die ersten Testfälle hat die Methode auch bestanden. Vielleicht findet ihr ja noch ein Denkfehler oder einen Weg etwas mehr Leistung herauszuholen.. Die Methode spezialisiert sich auf byte arrays.

public void searchForSameData(Map<byte[], byte[]> map1, Map<byte[], byte[]> map2){
		for (Entry<byte[], byte[]> dataFromMap1 : map1.entrySet()) {
			for (Entry<byte[], byte[]> dataFromMap2 : map2.entrySet()) {
				if(containesSameData(dataFromMap1.getKey(), dataFromMap2.getKey())){
					if(containesSameData(dataFromMap1.getValue(), dataFromMap2.getValue())){
						System.out.println("Found same data");
					}
				}
			}
		}
	}
	
	
	private boolean containsSameData(byte[] b1, byte[] b2){
		if(ByteBuffer.wrap(b1).equals(ByteBuffer.wrap(b2))){
			return true;
		}
		
		return false;
	}

 

[Marco13]

Das dürfte bei vielen Elementen ziemlich langsam werden, zumindest ist es in O(n^2) (bzw. O(m*n)).

Kann der Key-Typ der Map geändert werden? Wenn der gleich ein ByteBuffer wäre, wäre das einfacher/effizienter möglich...

 

[DrZoidberg]

Also wenn we performant sein soll, dann kannst du als Key keine Array verwenden und du kannst auch keine verschachtelten Schleifen nehmen.

So könnte es aussehen

public void searchForSameData(Map<ByteBuffer, byte[]> map1, Map<ByteBuffer, byte[]> map2){
        if(map1.size() > map2.size()) {
            Map<ByteBuffer, byte[]> temp = map1;
            map1 = map2;
            map2 = temp;
        }
        for (Map.Entry<ByteBuffer, byte[]> dataFromMap1 : map1.entrySet()) {
            byte[] value2 = map2.get(dataFromMap1.getKey());
            if(value2 != null && Arrays.equals(value2, dataFromMap1.getValue())) {
                 System.out.println("Found same data");
            }
        }
    }

 

[XPrototypeX]

Naja, die Daten kommen von einer Text datei und werden byte weiße eingelesen. Es ist sicher möglich die einzelnen Bytes in einen ByteBuffer einzulesen.

Edit: Ich habe mal in die API geschaut. Ich kann auch beide Werte als ByteBuffer einlesen. Das sollte kein Problem darstellen.

 

[Spacerat]

...und was ist das für Text? UTF8? Unicode? ASCII? Egal... Wenn's richtig Performant sein soll, würde ich die gesammte Datei in einen einzigen DirectByteBuffer lesen und diese Buffer splitten, bzw. slicen. Das hat den Vorteil, dass all die entstehenden Teilbuffer nur einmal Speicher verschwenden.

 

[XPrototypeX]

könntest du das etwas spezifischer erklären?^^

 

[Spacerat]

Alle Kindbuffer eines Buffers teilen sich die Datengrundlage. Bei 'nem Heapbuffer wäre es das jewilige Array (byte[], char[], int[] usw.) und bei 'nem DirectBuffer Hauptspeicher der Klasse "Unsafe" (unsafe für die VM, weil vom BS verwaltet). Kindbuffer bekommen nur eigene (und damit unabhängige) Positions- Limit- und Capacitypointer (wobei letzterer stets final ist). Änderungen an den Daten (bis auf die Pointer) durch einen der Buffer werden ausnahmslos sofort auch in allen anderen Buffern sichtbar. Musst dich evtl. mal in NIO-Buffers einlesen.

 

[DrZoidberg]

Du könntest auch Strings verwenden. Die teilen sich auch das selbe char array, wenn sie gesplitted werden.
Wie sehen diese Textdateien denn aus?

 

[Spacerat]

Du könntest auch Strings verwenden. Die teilen sich auch das selbe char array, wenn sie gesplitted werden.
Wie sehen diese Textdateien denn aus?

Das würde ich mir bei Java1.7 aber noch mal genauer im Quelltext anschauen... Der einzig verbliebene String-Konstruktor, der "Arrays.copyOfRange()" nicht verwendet ist package private, wird nur 5 Mal verwendet und "<String>.split()" gehört nicht dazu.
Seit Java1.7 können Strings in Switch-Case verwendet werden. Weil dafür aber für die gesamte Laufzeit über konstante Werte notwendig sind, hat man dazu wohl die Startadresse des Char-Arrays verwendet und das hatte zur Folge, dass sich nur noch sehr wenige Strings eines teilen dürfen (nur rein hypothetisch).

 

[XPrototypeX]

Also die Text-Datei basiert auf immer gleich langen Zeilen. Ich lese Zeilenweiße die Bytes in einem BufferedInputStream ein. Jede Zeile hat einen uniquen Schlüssel (der Key) und restliche Daten (value). Im moment Teile ich das Byte Array mit Arrys.copyOfRange(). So lange halt bis das ende der Datei erreicht ist.

 

[XPrototypeX]

So hab den Input jetzt mal anders gelöst (NIO) und habe einen ByteBuffer als Key und als Value verwendet.

BufferedInputStream bis = null;
		FileInputStream fis = null; 
		
			
		
			bis = new BufferedInputStream(new FileInputStream(file));
			/*
			 * Java NIO
			 */

			fis = new FileInputStream(file);
			FileChannel fileChannel = fis.getChannel();
			ByteBuffer byteBufferKey = ByteBuffer.allocate(59);
			ByteBuffer byteBufferValue = ByteBuffer.allocate(142);

			int bytesKey = fileChannel.read(byteBufferKey);
			int bytesValue = fileChannel.read(byteBufferValue);
			while (bytesKey != -1 && bytesValue != -1) {
				byteBufferKey.flip();
				byteBufferValue.flip();
				
				dataNew.put(byteBufferKey, byteBufferValue);
				
				
				byteBufferKey.clear();
				byteBufferValue.clear();
				bytesKey = fileChannel.read(byteBufferKey);
				bytesValue = fileChannel.read(byteBufferValue);
			}
			if (fis != null) {
				fis.close();
			}

Vorher hatte ich das übrigends so:

	/*
			 * Java I/O
			 */
			//
			 byte[] buffer = new byte[201];
			 int length;
		
			 while((length=bis.read(buffer))!=-1){
			
			 data.put(Arrays.copyOfRange(buffer, 0, 59), Arrays.copyOfRange(buffer, 60, 201));
			
			
			
			 }
			
			 System.out.println(data.size());

 

[Spacerat]

Da ist noch ein Haken, und zwar liest du beide Buffer 2 Mal ein. Beim 2. Lesen, wird der Erste Teil überschrieben. Das ändert auch die Daten der bereits in der Map (dataNew) gespeicherten Buffer, das bedeutet, du hast am Ende Zeilen * gleiche Key-Value-Paare in der Map, also sprich, nur einen.
Sinnvoller wäre es, wenn du die Datei in einen einzigen grossen ByteBuffer lädst und dann jeweils mit "duplicate()" "position(newValue)" "limit(newValue)" und "asReadOnlyBuffer()" diesen grossen ByteBuffer teilst und die Einzelteile in der Map speicherst.

 

[XPrototypeX]

Okay danke hab ich gemacht. Übrigends beide Methoden sind ungefähr gleich schnell (unterscheided sich nur in Millisekunden). Jedoch zeigt mir leider die NIO Methode 400 Zeilen zu wenig an. An was könnte das liegen?

Nochmal meine neue Funktion:

BufferedInputStream bis = null;
		FileInputStream fis = null; 
		try {
			
		
			bis = new BufferedInputStream(new FileInputStream(file));
			/*
			 * Java NIO
			 */

			fis = new FileInputStream(file);
			FileChannel fileChannel = fis.getChannel();
			ByteBuffer byteBuffer = ByteBuffer.allocate(201);

			int bytes = fileChannel.read(byteBuffer);
		
			while (bytes != -1) {
				byteBuffer.flip();
			
				
				dataNew.put(byteBuffer.asReadOnlyBuffer().duplicate().position(0).limit(59), byteBuffer.asReadOnlyBuffer().duplicate().position(60).limit(201));
				
				
			
				byteBuffer.clear();
				bytes = fileChannel.read(byteBuffer);
				
			}
			if (fis != null) {
				fis.close();
			}

			System.out.println(dataNew.size());

Die Methode die doppelte Einträge checkt habe ich übrigends so modifiziert :

 if(currData.size() > lastData.size()) {
		            Map<Buffer, Buffer> temp = currData;
		            currData = lastData;
		            currData = temp;
		        }
		        for (Entry<Buffer, Buffer> dataFromMap1 : currData.entrySet()) {
		            Buffer key = lastData.get(dataFromMap1.getKey());
		            Buffer value = lastData.get(dataFromMap1.getValue());
		            
		            if(key != null){
		            	if(value != null){
		            		break;
		            	}else{
		            		zaehlerChanges ++;
		            	}
		            }else{
		            	zaehlerNew ++;
		            }
		        }

Werde diese Methode auch noch etwas optimieren, da auch diese nicht alle Werte richtig ausgibt.

 

[Spacerat]

Las mich raten: Die Datei hat aber eigentlich 401 Zeilen. :lol:
Ich hab' dir mal 'nen KSKB gebaut. Mit Buffern ist's wohl erst einfach, wenn man's erst paar mal gemacht hat.

import java.io.ByteArrayOutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.nio.ByteBuffer;
import java.util.Map;
import java.util.Map.Entry;
import java.util.TreeMap;

public class LocaleTest {
	public static void main(String[] args) throws IOException {
		Map<ByteBuffer, ByteBuffer> data = new TreeMap<>();
		InputStream in = LocaleTest.class.getResourceAsStream("LocaleTest.locale");
		ByteArrayOutputStream out = new ByteArrayOutputStream();
		int r;
		while((r = in.read()) != -1) {
			out.write(r);
		}
		in.close();
		out.close();
		ByteBuffer localeData = ByteBuffer.wrap(out.toByteArray());
		ByteBuffer key, value;
		key = null;
		int p = localeData.position();
		do {
			char c = (char) (localeData.get() & 0xFF);
			if(c == '=') {
				key = localeData.duplicate();
				key.position(p);
				p = localeData.position();
				key.limit(p - 1);
				key = key.slice();
			} else if(c == '\n') {
				value = localeData.duplicate();
				value.position(p);
				p = localeData.position();
				value.limit(p - 1);
				value = value.slice();
				data.put(key.asReadOnlyBuffer(), value.asReadOnlyBuffer());
				key = null;
				value = null;
			}
		} while(localeData.position() < localeData.capacity());
		if(key != null) {
			value = localeData.duplicate();
			value.position(p);
			p = localeData.position();
			value.limit(p);
			value = value.slice();
			data.put(key.asReadOnlyBuffer(), value.asReadOnlyBuffer());
			key = null;
			value = null;
		}
		byte[] b = null;
		for(Entry<ByteBuffer, ByteBuffer> e : data.entrySet()) {
			key = e.getKey();
			value = e.getValue();
			if(b == null || b.length < key.capacity()) {
				b = new byte[key.capacity()];
			}
			key.get(b, 0, key.capacity());
			String k = new String(b, 0, key.capacity());
			if(b.length < value.capacity()) {
				b = new byte[value.capacity()];
			}
			value.get(b, 0, value.capacity());
			String v = new String(b, 0, value.capacity());
			System.out.print(String.format("%s=%s", k, v));
		}
	}
}

Das Ganze liest eine Property-Datei ein, so wie man sie von Java her gewohnt ist. Die Korrekturen des Pointers p (p - 1) eliminieren die Gleichzeichen und LineFeeds. In Eclipse kann man bei der Verwendung von Heapbuffern nachvollziehen, dass alle Buffer auf ein und dasselbe Array zurückgreifen, jedoch alle verschielene Limits, Pointer und Kapazitäten haben.

 

[XPrototypeX]

Las mich raten: Die Datei hat aber eigentlich 401 Zeilen. :lol:

Schön wär's. Dann wüsste ich wenigstens das etwsa mit dem einlesen an sich nicht stimmt

Aber leider hat er eine abweichung von 400 Zeilen bei etwas mehr als 1mio Einträgen :|

Das mit den Buffern und generell NIO ist neu für mich danke für das Beispiel hab meinen Code jetzt nochmal angepasst. Ich denke es hat etwas mit dem 201 großem Bytebuffer zu tun. Eine Zeile hat 200 bytes (201 mit dem line seperator byte) . Wahrscheinlich vergisst er da ab und an mal eins was eigentlich ziemlich schlecht ist. Ich bin am Überlegen ob ich einen String nehme und diesen einfach vergleiche das dauert zwar länger dafür funktioniert es dann aber auch. ;(

		BufferedInputStream bis = null;
		FileInputStream fis = null;
		try {

			bis = new BufferedInputStream(new FileInputStream(file));
			 /*
			 * Java NIO
			 */
			
			 fis = new FileInputStream(file);
			 FileChannel fileChannel = fis.getChannel();
			 ByteBuffer byteBuffer = ByteBuffer.allocate(201);
			 ByteBuffer k, v; 
			 int bytes = fileChannel.read(byteBuffer);
			
			 while (bytes != -1) {
			 byteBuffer.flip();
			
			 k = byteBuffer.duplicate();
			 k.position(0);
			 k.limit(59);
			 k.slice();
			 
			 v = byteBuffer.duplicate();
			 v.position(60);
			 v.limit(201);
			 v.slice();
			    
			 
			 
			 dataNew.put(k.asReadOnlyBuffer(),v.asReadOnlyBuffer());
			
			 v = null;
			 k = null; 
			
			
			 byteBuffer.clear();
			 bytes = fileChannel.read(byteBuffer);
			
			 }
			 if (fis != null) {
			 fis.close();
			 }

 

[Spacerat]

Ich frage mich die ganze Zeit, warum du nicht erst die ganze Datei in einen einzigen Datenpuffer liest (so wie ich ). Danach kannst du Pointer und Limits setzen (Ich mach das, indem ich auf "=" und "\n" prüfe), die Buffer slicen und in die Map schreiben. Wie gesagt: Du erstellst dann zwar haufenweise Buffer, die arbeiten dann aber so, wie es einst der Stringpool-Buffer tat (Vergangenheit, weil es für mich so aussieht, als gäbe es ihn seit Java7 nicht mehr ???:L).
Im Prinzip müsstest du dazu ja bei meinem KSKB nur die Zeile 12, dass deine Datei gelesen wird und die Bedingung für den Key ("if(c == '=')") duch einen Counter bis 60 ersetzen, den du nach dem Einfügen in die Map wieder zurücksetzt. Die Bedingung für die Value wäre ja dieselbe - ein Zeilenende.

 

[XPrototypeX]

Ok, habe ich gerade mal so gemacht. Aber irgendwie komme ich mit den Buffern auf keinen grünen Zweig..
Da ist meine While.
Der Fehler:

Exception in thread "Thread-0" java.lang.IllegalArgumentException
at java.nio.Buffer.limit(Buffer.java:249)
at model.FilesEinlesen.reaDataNew(FilesEinlesen.java:199)
at model.FilesEinlesen.run(FilesEinlesen.java:37)
at java.lang.Thread.run(Thread.java:619)

Jedoch lässt sich die Kapazität von dem ByteBuffer perfekt durch 201 teilen. Also liesst er schonmal richtig ein (Dafür verwende ich übrigends meine eigene NIO Methode, da große Daten per Channel schneller eingelesen werden solllen.

do {
			char c = (char) (localeData.get() & 0xFF);
			if (c == '\n') {
				p = localeData.position();
				key = localeData.duplicate();
				key.position(p);
				key.limit(p+59);
				key = key.slice();
				
				value = localeData.duplicate();
				value.position(p+60);
				value.limit(p+200);
				
				value = value.slice();
				
				dataNew.put(key.asReadOnlyBuffer(), value.asReadOnlyBuffer());
				
				key = null;
				value = null;
			}
			
	
		} while (localeData.position() < localeData.capacity());

 

[Spacerat]

Bin mir nicht sicher, aber ist es möglich, dass du die Positionen in die falsche Richtung setzt?
"p" sollte im ersten Durchlauf 0 sein, ist aber (evtl.) 201, also die Position der ersten Zeilenschaltung.
Vorschlag: "p" vor der "do-while" mit 0 initialisieren und erst am Ende der Slicevorgänge aktualisieren. Sonst unterschlägst du die erste Zeile und landest in den nächsten Durchläufen in bereits zugewiesenen Bereichen des Buffers.
Alternativ: den Positionszeiger so lassen wie er ist, beim Key Position p-201 und Limit p-142 und bei der Value Position p-143 und Limit p-1 setzen.