Para mejorar este coste, se usará una tabla hash o tabla de dispersión en la que guardaremos los coeficientes no nulos de un polinomio, junto con el exponente o grado correspondiente.

Veamos esta opción cuando usamos encadenamiento para la resolución de colisiones:

-- Tomamos max un primo mayor que el número máximo de coeficientes no 

-- nulos.

max: constant:=1039;

type ptMonomio;

-- El tipo monomio corresponde a un coeficiente no nulo del polinomio 

type monomio is

 record

  coeficiente:real;

  exponente:integer range 0..integer'last;

  sig:ptMonomio;

 end record;

type ptmonomio is access monomio;

-- El tipo polinomio es una tabla hash de monomios, con encadenamiento

type polinomio is array(integer range 0..max-1) of ptMonomio;

function h(k:integer) return integer is

-- esta es la función hash

begin

 return k mod max;

end h;

Necesitamos una operación que cree el polinomio vacío (p=0):
 

procedure vacio(p:out polinomio) is 

begin

 for i in 0..max-1 loop

  p(i):=null;

 end loop;

end vacio;

A continuación implementamos la operación añadir, 
 

procedure anadir(p:in out polinomio; m:in ptMonomio) is

--Pre: p=p0, m<>0

--Post: p=añadir(p,m.coeficiente, m.exponente)

k: integer; q:ptMonomio;

begin

 k:=h(m.exponente);

 -- m debe ser añadido a la lista que está en p(k)

 if p(k)=null then

  p(k):=new monomio'(m.coeficiente, m.exponente, null);

 else

  q:=p(k);

  while q.sig/=null and q.exponente/=m.exponente loop

   q:=q.sig;

  end loop;

  if q.exponente=m.exponente then

   q.coeficiente:=q.coeficiente+m.coeficiente;

   -- en este caso el coeficiente puede quedar 0,

   -- se puede modificar para evitarlo (ejercicio)

  else 

   q.sig:= new monomio'(m.coeficiente, m.exponente, null);

  end if;

 end if;

end anadir;

Consultar se implementa de forma similar, salvo que en este caso si la búsqueda no tiene éxito se devuelve 0.
 

function consultar(p:polinomio; n:integer) return real is

-- devuelve el coeficiente de grado n de p.

k: integer; q:ptMonomio;

begin

k:=h(n);

q:=p(k);

-- busco el coeficiente de grado n en la lista p(k)

while q/=null and then q.exponente/=n loop

q:=q.sig;

end loop;

if q/=null then

return q.coeficiente;

else 

--no está, luego es 0

return 0; 

end if;

end consultar;

El coste de las operaciones añadir y consultar en este caso depende de la longitud de las listas que guardamos en la tabla hash, es decir, de la cantidad de monomios no nulos del polinomio que la función hash envía a la misma posición de la tabla. Si hacemos la media entre todos los posibles polinomios, la longitud de estas listas es una constante pequeña. Esto quiere decir que para la mayoría de los polinomios, esta representación hará que las operaciones añadir y consultar tarden tiempo constante.

Ejercicio: hacer un programa que compruebe experimentalmente que esta función hash reparte bien.

Se deja como ejercicio implementar las operaciones de suma y producto y estudiar su coste.