Ayuda estructura de Datos

Hola compañeros estoy en la uni casi terminando materias y estoy parado dado que he tratado de buscar un código de funcionamiento de un método hash de plegamiento quiero ver un código como esta compuesto y razonar su funcionamiento pero no he tenido suerte. Alguien me podría ayudar con un ejemplo para ver y razonar su funciónamiento. De antemano les doy las gracias por su tiempo y atención

Opciones de visualización de comentarios

Seleccione la forma que prefiera para mostrar los comentarios y haga clic en «Guardar las opciones» para activar los cambios.

No sé si java.util.HashMap

No sé si java.util.HashMap utilice hash de plegamiento, pero puedes revisar el código para ver como lo hace:

http://www.docjar.com/html/api/java/util/HashMap.java.html

Acá hay un video que lo explica....

https://www.youtube.com/watch?v=IjYqbi9cioU

Imagen de Cid

Un ejemplo con cadenas

Encontre un ejemplo de hash de plegamiento (folding) con cadenas espero te sirva:

http://research.cs.vt.edu/AVresearch/hashing/strings.php

Imagen de zaskiel

gracias amigo

Gracias amigo leere un poco el tema gracias

Imagen de zaskiel

gracias amigo

Muchas gracias bro leere y me pondre manos a la obra

Imagen de zaskiel

gracias amigo

gracias carnal

Inventar nuestra propia función hash

Si leemos de qué se trata este método en Wikipedia:

Consiste en dividir el número en diferentes partes, y operar con ellas (normalmente con suma o multiplicación). También se produce colisión. Por ejemplo, si dividimos el número de 7 cifras en 2, 2 y 3 cifras y se suman, dará otro número de tres cifras (y si no, se toman las tres últimas cifras):

5700931 → 57 + 00 + 931 = 988
3498610 → 34 + 98 + 610 = 742
0056241 → 00 + 56 + 241 = 297
9134720 → 91 + 34 + 720 = 845
5174929 → 51 + 74 + 929 = 1054

Nota: Estas solo son sugerencias y que con cada problema se pude implementar una nueva función hash que incluso tu puedes inventar o formular.

Nosotros podemos inventar nuestra propia función hash. Se me ocurre, por ejemplo, dividir un número positivo (si trabajásemos con números) en grupos de miles. Por ejemplo: 5700931 → 5,700,931 → 5 + 700 + 931 = 1636. Si tomo los tres último digitos, entonces el resultado es 636. En Java:

public int buscarHash(int numero) {
    int suma = 0;
    while (numero > 0) {
        int parte = numero % 1000;
        suma += parte;
        numero /= 1000;
    }
    return suma % 1000;
}

Esta función hash devuelve de 0 a 999 para cualquier entero positivo (int). Si mi tabla hash tuviera 10 cubetas, entonces pondría aquellas claves con hash 0 a 99 en la primera cubeta (índice 0), de 100 a 199 en la segunda cubeta (índice 1) y así sucesivamente. Es decir:

int valorHash = buscarHash(5700931); // 636
int indiceCubeta = valorHash / 100; // 6
Imagen de joseguru

Esto te puede ayudar!!!!

    import java.util.Collection;

    import java.util.HashMap;

    import java.util.Iterator;

    import java.util.Map;

    import java.util.Map.Entry;

    import java.util.Set;

     

    public class HashMapImpl<K, V>

    {

        private HashMap<K, V> hashMap;

     

        /*

         * Constructs an empty HashMap with the default initial capacity (16) and

         * the default load factor (0.75).

         */

        public HashMapImpl()

        {

            hashMap = new HashMap<K, V>();

        }

     

        /*

         * Constructs an empty HashMap with the specified initial capacity and the

         * default load factor (0.75).

         */

        public HashMapImpl(int initialCapacity)

        {

            hashMap = new HashMap<K, V>(initialCapacity);

        }

     

        /*

         * Constructs an empty HashMap with the specified initial capacity and load

         * factor.

         */

        public HashMapImpl(int initialCapacity, float loadFactor)

        {

            hashMap = new HashMap<K, V>(initialCapacity, loadFactor);

        }

     

        /* Constructs a new HashMap with the same mappings as the specified Map. */

        public HashMapImpl(Map<? extends K, ? extends V> m)

        {

            hashMap = new HashMap<K, V>(m);

        }

     

        /* Removes all of the mappings from this map. */

        public void clear()

        {

            hashMap.clear();

        }

     

        /*

         * Returns a shallow copy of this HashMap instance: the keys and values

         * themselves are not cloned.

         */

        public Object clone()

        {

            return hashMap.clone();

        }

     

        /* Returns true if this map contains a mapping for the specified key. */

        public boolean containsKey(Object key)

        {

            return hashMap.containsKey(key);

        }

     

        /* Returns true if this map maps one or more keys to the specified value. */

        public boolean containsValue(Object value)

        {

            return hashMap.containsValue(value);

        }

     

        /* Returns a Set view of the mappings contained in this map. */

        public Set<Map.Entry<K, V>> entrySet()

        {

            return hashMap.entrySet();

        }

     

        /*

         * Returns the value to which the specified key is mapped, or null if this

         * map contains no mapping for the key.

         */

        public V get(Object key)

        {

            return hashMap.get(key);

        }

     

        /* Returns true if this map contains no key-value mappings. */

        public boolean isEmpty()

        {

            return hashMap.isEmpty();

        }

     

        /* Returns a Set view of the keys contained in this map. */

        public Set<K> keySet()

        {

            return hashMap.keySet();

        }

     

        /* Associates the specified value with the specified key in this map. */

        public V put(K key, V value)

        {

            return hashMap.put(key, value);

        }

     

        /* Copies all of the mappings from the specified map to this map. */

        public void putAll(Map<? extends K, ? extends V> m)

        {

            hashMap.putAll(m);

        }

     

        /* Removes the mapping for the specified key from this map if present. */

        public V remove(Object key)

        {

            return hashMap.remove(key);

        }

     

        /* Returns the number of key-value mappings in this map. */

        public int size()

        {

            return hashMap.size();

        }

     

        /* Returns a Collection view of the values contained in this map. */

        public Collection<V> values()

        {

            return hashMap.values();

        }

     

        public static void main(String... arg)

        {

            HashMapImpl<Integer, Integer> hashMap = new HashMapImpl<Integer, Integer>();

     

            hashMap.put(1, 100);

            hashMap.put(2, 200);

            hashMap.put(3, 300);

     

            Map<Integer, Integer> anotherMap = new HashMap<Integer, Integer>();

            anotherMap.put(4, 400);

            anotherMap.put(5, 500);

     

            hashMap.putAll(anotherMap);

     

            System.out.println("the key set of the map is ");

            Set<Integer> keySet = hashMap.keySet();

            Iterator<Integer> itr = keySet.iterator();

            while (itr.hasNext())

            {

                System.out.print(itr.next() + "\t");

            }

            System.out.println();

     

            System.out.println("the values of the map is ");

            Collection<Integer> collectionValues = hashMap.values();

            itr = collectionValues.iterator();

            while (itr.hasNext())

            {

                System.out.print(itr.next() + "\t");

            }

            System.out.println();

     

            System.out.println("the entry set of the map is ");

            Iterator<Entry<Integer, Integer>> eitr;

            Set<Entry<Integer, Integer>> entrySet = hashMap.entrySet();

            eitr = entrySet.iterator();

            while (eitr.hasNext())

            {

                System.out.println(eitr.next() + "\t");

            }

            System.out.println("the hash Map contains Key 3 :" + hashMap.containsKey(3));

            System.out.println("the hash Map contains Value 600 :" + hashMap.containsValue(600));

            System.out.println("the size of the hash Map is " + hashMap.size());

            hashMap.clear();

            if (hashMap.isEmpty())

                System.out.println("the hash Map is empty");

            else

                System.out.println("the hash Map is not empty");

        }


Salida-->

$javac HashMapImpl.java
$java HashMapImpl
the key set of the map is
1       2       3       4       5      
the values of the map is
100     200     300     400     500    
the entry set of the map is
1=100  
2=200  
3=300  
4=400  
5=500  
the hash Map contains Key 3 :true
the hash Map contains Value 600 :false
the size of the hash Map is 5
the hash Map is empty